题解 | #矩阵中的路径#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int nex[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
    vector<vector<char> > mp;
    bool vis[30][30];
    bool flag;
    void dfs(int x,int y,string word,string now,int index){
        cout << now << endl;
        if(now==word){
             flag = true;
            return ;
        }
        for(int i=0; i<4; i++){
            int xx = x + nex[i][0];
            int yy = y + nex[i][1];
            if(xx<mp.size() && xx>=0 && yy<mp[xx].size() && yy>=0 && !vis[xx][yy] && mp[xx][yy]==word[index]){
                vis[xx][yy] = 1;
                now += mp[xx][yy];
                dfs(xx,yy,word,now,index+1);
                vis[xx][yy] = 0;
                now.pop_back();
            }
        }
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        mp = matrix; 
        flag = false;
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[i].size(); j++){
                if(matrix[i][j]==word[0]){
                    for(int k=0; k<30; k++)
                        for(int h=0; h<30; h++)
                            vis[k][h] = 0;
                
                    string t = "";
                    t += word[0];
                    dfs(i,j,word,t,1);
                    if(flag) return true;
                }
            }
        }
        return false;
    }
};