题解 | #单词搜索#

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