题解 | #矩阵中的路径#

#include <string>
#include <type_traits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    //判断该格子经历次数(只能经历一次)
    int flag[25][25]={0};
    int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
    bool find(vector<vector<char> >& matrix,int n,int x,int y,string word,string temp) {
        // if(x>=matrix.size()||x<0||y>=matrix[0].size()||y<0||matrix[x][y]!=word[n])
        // {
        //     return;
        // }
        
        if(n>=word.size()-1&&temp==word) {
            return true;
        }
        bool res;
        for(int i=0;i<=3;i++) {
            x=x+dxy[i][0];
            y=y+dxy[i][1];
            if(flag[x][y]==0&&!(x>=matrix.size()||x<0||y>=matrix[0].size()||y<0)){
                flag[x][y]=1;
                temp=temp+matrix[x][y];
                if(matrix[x][y]==word[n+1])res=find(matrix,n+1,x,y,word,temp);
                temp.pop_back();
                flag[x][y]=0;
            }
            x=x-dxy[i][0];
            y=y-dxy[i][1];
        }
        return res;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        string temp;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                if(matrix[i][j]==word[0]) {
                    flag[i][j]=true;
                    temp.push_back(word[0]);
                    if(find(matrix,0,i,j,word,temp)) return true;
                    temp.pop_back();
                    flag[i][j]=false;
                }
            }
        }
        return false;
    }
};