题解 | #矩阵中的路径#

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