题解 | #矩阵中的路径#

先放代码：

class Solution {
public:
    bool hasPath(vector<vector<char> >& matrix, string word) {
        int n = matrix.size(), m = matrix[0].size();
        int vis[205][205];
        //对vis矩阵进行初始化
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j] == word[0]){
                    if(dfs(matrix, word, vis, i, j, 1, n, m)){
                        return true;
                    }
                    //状态恢复
                    vis[i][j]=0;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& matrix, string word, int vis[][205], int x, int y, int p, int n, int m){
        //如果p等于word的长度，查找成功，返回true
        if(p == word.size()){
            return true;
        }
        //走过的元素不能再走，所以vis设置为1
        vis[x][y] = 1;
        //像四个方向的偏移量，分别是上，右，下，左
        int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for(int i=0; i<4; i++){
            int dx = x+dxy[i][0], dy = y+dxy[i][1];
            if(dx>=0 && dx<n && dy>=0 && dy<m && !vis[dx][dy] && matrix[dx][dy]==word[p]){
                if(dfs(matrix, word, vis, dx, dy, p+1, n, m)){
                    return true;
                }
                //恢复状态
                vis[dx][dy]=0;
            }
        }
        return false;
    }
};