题解 | #单词搜索#

dfs算法，走过的每一步置为0，防止再次走过，都走不通则回溯。

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