题解 | #矩阵中的路径#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool dfs(vector<vector<char>> &matrix,int n,int m,int i,int j,string word,int k,vector<vector<bool>>& flag)
    {
        if (i<0||i>=n||j<0||j>=m||(matrix[i][j]!=word[k])||flag[i][j]==true){  
            return false;
        }
        if (k==word.length()-1) {
            return true;
        }
        flag[i][j]=true;
        if(dfs(matrix,n,m,i-1,j,word,k+1,flag)
        ||dfs(matrix,n,m,i+1,j,word,k+1,flag)
        ||dfs(matrix,n,m,i,j-1,word,k+1,flag)
        ||dfs(matrix,n,m,i,j+1,word,k+1,flag))
        {
            return true;
        }
        flag[i][j]=false;
        return false;
    }
    

    bool hasPath(vector<vector<char>>& matrix, string word) {
        if (matrix.size()==0) {
            return false;
        }
        int n=matrix.size();
        int m=matrix[0].size();
        vector<vector<bool>> flag(n,vector<bool>(m,false));
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (dfs(matrix,n,m,i,j,word,0,flag)) {
                    return true;
                }
            }
        }
    return false;
    }
};

深度优先搜索，注意