题解 | #单词搜索#

#include <string>
class Solution {
public:

    bool exist(vector<string>& board, string word) {
        // write code here
        int m=board.size();
        if(m<= 0) return false;
        int n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (dfs(0,board,word,i,j)) {
                    return true;
                }
            }
        }
        return false;

    }
    bool dfs(int cur,vector<string>& board, string word,int i,int j){
        if (cur==word.length()) return true;
        if (i>=0&&i<board.size()&&j>=0&&j<=board[0].size()&&board[i][j]==word[cur]) {
            char temp=board[i][j];
            board[i][j]=0;//遍历过后将他置为0
            if(dfs(cur+1,board,word,i-1,j)) return true;
            if(dfs(cur+1,board,word,i,j+1)) return true;
            if(dfs(cur+1,board,word,i+1,j)) return true;
            if(dfs(cur+1,board,word,i,j-1)) return true;
            board[i][j]=temp;//遍历结束重置
        }
        return false;
    }
};