题解

题目难度：简单

知识点：DFS、字符串、

方法（一）：

第一步：获取单词的首字符
第二步：在字符迷阵中找到该字符
第三步：字符迷阵中从该字符开始，从水平、垂直、右下角方向与单词字符逐一比较
【注1】：在逐一比较时要考虑字符迷阵的边界，即m、n，访问字符迷阵时数组越界问题。
【注2】：当我们在考虑三个方向是，只考虑水平向左、垂直向下、右下角方向，字符迷阵中计数单词时不会重复计数。

#include<iostream>
#include<vector>
#include<string>
#define Maxn 100 
using namespace std;
string a[Maxn];
int main(){
    int T;
    cin>>T;
    while(T){
        int m,n;
        cin>>m>>n;
        for(int i=0;i<m;i++){
             cin>>a[i];
        }
        string word;
        cin>>word;
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(a[i][j]==word[0]){
                    //水平方向
                    int flat=1;
                    for(int k=0;k<word.length();k++){
                        if((j+k>=n)||(a[i][j+k]!=word[k])) {
                            flat=0;
                            break;
                        }
                    } 
                    if(flat) count++;
                    //垂直方向 
                    flat=1;
                    for(int k=0;k<word.length();k++){
                        if((i+k>=m)||a[i+k][j]!=word[k]){
                            flat=0;
                            break;
                        }
                    } 
                    if(flat) count++;
                    //右下角方向
                    flat=1;
                    for(int k=0;k<word.length();k++){
                        if((i+k>=m)||(j+k>=n)||a[i+k][j+k]!=word[k]){
                            flat=0;
                            break;
                        }
                    } 
                    if(flat) count++;

                }
            }
        }
        cout<<count<<endl;
        T--;
    }
    return 0;
}

方法（二）

由于这里只能走固定的三个方向，我们可以采用常规的dfs方法。

简单分析:

1.dfs()方法中传入字符迷阵s1,单词s2,其中i、j代表当前访问的字符迷阵下标，k代表当前访问的单词下标。dir传入0、1、2，分别代表从当前位置向水平、垂直、右下角方向访问。该方法判断了从初始输入的i,j位置开始，dir方向是否为所要单词。

2.为该单词的判断条件时，当前访问的单词下标已经是单词长度，计数sum变量值加一。如果没有达到单词长度，再与单词比较之前考虑，i、j是否已经越界，如果没有越界就判断s1[i][j]与s2[k]的值是否相等，不相等直接结束。

3.如果相等，那么我们k+1,表示下一次比较的字符所对应的单词下标。这个，判断最初传入的dir方向，若为0，表示前面与单词比较都是按水平方向，那这时j+1,继续下一次dfs()。其他两个方向同理。

4.该dfs方法为初始传入的i、j确定的开始位置下标、dir方向是否是该单词。所以在main函数中用三重循环即可判断所有情况。

#include<iostream>
#include<string>
#define Maxn 100
using namespace std;
string s1[Maxn];
int sum=0;
void dfs(string* a,string s,int i,int j,int k,int dir,int m,int n){
    if(k==s.length()){
    //    cout<<i<<j<<endl;
        sum++;
        return ;
    }
    if(i==m||j==n||a[i][j]!=s[k]) return ;
    k++;
    if(dir==0)     dfs(a,s,i,j+1,k,dir,m,n);
    else if(dir==1) dfs(a,s,i+1,j,k,dir,m,n);
    else dfs(a,s,i+1,j+1,k,dir,m,n);    
}
int main(){
    int T;
    cin>>T;
    while(T){
        int m,n;
        cin>>m>>n;
        for(int i=0;i<m;i++){
            cin>>s1[i];
        }
        string s2;
        cin>>s2;
        sum=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int dir=0;dir<3;dir++){
                    dfs(s1,s2,i,j,0,dir,m,n);
                }
            }
        }
        cout<<sum<<endl;
        T--;
    }
    return 0;
}