题解 | #矩阵中的路径#

简单的dfs，做一下简单的判断即可，记得引用传参

class Solution {
public:
    vector<vector<bool>> search_map_;
    int row_;
    int col_;
    bool is_success_ = false;//
    void DFS(vector<vector<char> >& matrix,int x,int y,int cur,const string& word){
        if(is_success_)return;
        if(x >= row_||y >= col_ || x<0 || y<0 ){// limit
            return;
        }
        if(search_map_[x][y]== true || word[cur] != matrix[x][y]){
            // current char is not right or searched
            return;
        }
        if(cur == word.size()-1){// the last char
            is_success_ = true;
            return;
        }
        search_map_[x][y]=true;
        DFS(matrix,x+1,y,cur+1,word);
        DFS(matrix,x-1,y,cur+1,word);
        DFS(matrix,x,y+1,cur+1,word);
        DFS(matrix,x,y-1,cur+1,word);
        search_map_[x][y]=false; // reset search item
    }

    bool hasPath(vector<vector<char> >& matrix, string word) {
        if(matrix.empty()||word.empty()){
            return false;
        }
        row_ = matrix.size();
        col_  = matrix[0].size();
        for(int i=0;i<row_;i++){
            search_map_.push_back(vector<bool>(col_,false));
        }
        for(int i=0;i<row_;i++){
            for(int j=0;j<col_;j++){
                if(matrix[i][j] == word[0]){
                    DFS(matrix,i,j,0,word);
                    if(is_success_){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};