题解 | #矩阵中的路径#

#include <cstdio>
#include <cstring>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int nex[4][2]={{-1,0},{0,-1},{1,0},{0,1}};  //方向数组
    int book[25][25]={0};
    int cnt=0;
    bool dfsans=false;
    void dfs(int x,int y,string word,vector<vector<char> >& matrix){
        int n=word.size();
        book[x][y]=1;
        if(cnt==n-1&&matrix[x][y]==word[cnt]){dfsans=true;return;}//最后一个元素
        //cout << matrix[x][y]  << " " << cnt << word[cnt] <<  endl;
        for(int i=0;i<4;i++){
            int dx=x+nex[i][0];
            int dy=y+nex[i][1];
            //cout << dx << " " << dy << " " << word[cnt+1] << endl;
            if((dx>=0&&dx<matrix.size())&&(dy>=0&&dy<matrix[0].size())&&book[dx][dy]!=1&&matrix[dx][dy]==word[cnt+1]){
                //cout << dx << " " << dy << " " << word[cnt+1] << " " << matrix[dx][dy]<< endl;
                book[dx][dy]=1;
                cnt++;
                dfs(dx, dy,word,matrix);
                cnt--;//踩坑，这是回溯条件，如果方向不对，回溯的时候深度也要--；
                book[dx][dy]=0;//踩坑，回溯，标记数组也要回正
            }
        }
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        //对于字符串首字母匹配的位置，每一个都进行一遍dfs
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                if(matrix[i][j]==word[0]){
                    cnt=0;//记录dfs深度
                    memset(book, 0, sizeof(book));//局部变量不能直接用{0}赋值；
                    dfs(i,j,word,matrix);
                }
            }
        }
        return dfsans;
    }
};