题解 | #单词搜索#

1. 专门适用于true false 的模板。记得把base case 2放前，否则会超时

class Solution {
public:

    bool DFS(vector<vector<char> > &board,string word, int cur, int r, int c,vector<vector<bool> >& visits){

        //base case 2
        if(cur == word.size()){
            return true;
        }

        //bool 类型的方向数组 base 1
        if(c<0||c>=board[0].size()|| r<0|| r>=board.size()||visits[r][c]||board[r][c]!=word[cur]){
            return false;
        }





        bool res;

        visits[r][c] = true;
        res = DFS(board,word,cur+1,r+1,c,visits)||
              DFS(board,word,cur+1,r-1,c,visits)||
              DFS(board,word,cur+1,r,c+1,visits)||
              DFS(board,word,cur+1,r,c-1,visits);

        visits[r][c] = false;

        return res;

    }

    bool exist(vector<vector<char> > &board, string word) {
        if (!board.size()) return false;

        vector<vector<bool> > visits(board.size(),vector<bool>(board[0].size(),false));
        for(int i =0 ; i< board.size();i++){
            for(int j =0; j< board[0].size();j++){
                if(board[i][j]==word[0]){
                    if(DFS(board,word,0,i,j,visits)){
                        return true;
                    }
                }
            }
        }
        return false;


    }
};