题解 | #矩阵中的路径#

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

        if(k==word.size()-1){
            return true;
        }

        flag[i][j]=true;
        if(backtrack(matrix, word, m, n, i-1, j, k+1,flag)||backtrack(matrix, word, m, n, i+1, j, k+1,  flag)||backtrack(matrix, word, m, n, i, j-1, k+1,flag)||backtrack(matrix, word, m, n, i, j+1, k+1,flag)){
            return true;
        }else{
             flag[i][j]=false;
             return false;
        }


    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if(matrix.size()==0){
            return false;
        }
        int m=matrix.size();
        int n=matrix[0].size();

        vector<vector<bool>>flag(m,vector<bool>(n,false));
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
               if(backtrack(matrix, word, m, n, i, j, 0,flag)) {
                return true;
               }
            }
        }
         return false;
    }

   
};