简单的DFS
代码语言：javascript复制class Solution {
public:
int vis[1005][1005];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool exist(vector<vector<char>>& board, string word) {
if(word.length()==0)
return false;
for(int i=0;i<board.size();i )
{
for(int j=0;j<board[i].size();j )
{
if(board[i][j]==word[0])
{
vis[i][j]=1;
bool ans=dfs(word,board,i,j,1);
if(ans==true)
return true;
vis[i][j]=0;
}
}
}
return false;
}
bool dfs(string word,vector<vector<char>> board,int x,int y,int k)
{
if(k==word.length())
{
return true;
}
for(int i=0;i<4;i )
{
x =dir[i][0];
y =dir[i][1];
if(x>=0&&x<board.size()&&y>=0&&y<board[0].size()
&&vis[x][y]==0)
{
if(board[x][y]==word[k])
{
vis[x][y]=1;
bool res= dfs(word,board,x,y,k 1);
vis[x][y]=0;
if(res==true)
return true;
}
}
x-=dir[i][0];
y-=dir[i][1];
}
return false;
}
};
