题解 | #矩阵中的路径#

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

    bool dfs(vector<vector<char> >& matrix, int row, int col, int i, int j, int len, string word, vector<vector<bool> >& flag){
        if(i <0 || i >= row || j < 0 || j >= col){
            return false;
        }
        if((matrix[i][j] != word[len]) || (flag[i][j] == true)){
            return false;
        }
        if(len == word.length()-1){
            return true;
        }

        flag[i][j] = true;
        if(    dfs(matrix, row, col, i-1, j, len+1, word, flag)
            || dfs(matrix, row, col, i+1, j, len+1, word, flag)
            || dfs(matrix, row, col, i, j-1, len+1, word, flag)
            || dfs(matrix, row, col, i, j+1, len+1, word, flag)){
            return true;
        }
        flag[i][j] = false;
        return false;
    }
};