题解 | #单词搜索#

class Solution {
public:

     bool arr[101][101] = { 0 };//用来标记该位置是否查询过
     int n,m;
     int dy[4]={1,-1,0,0};
     int dx[4]={0,0,1,-1};

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

    bool dfs(int i,int j,vector<string>& board, string& word,int pos)
    {
        if(pos == word.size()-1)
        {
            return true;
        }
        arr[i][j] = true;//标记查询位置
        for(int k=0;k<4;k++)
        {
            int a = i + dx[k];
            int b = j + dy[k];
            if(a>=0 && a<n && b>=0 && b<m && !arr[a][b] && board[a][b]==word[pos+1]) 
            {
                if(dfs(a,b,board,word,pos+1)) return true;
            }
        }
        arr[i][j] = false;//撤销查询位置
        return false;
    }
    
};