1.bfs没法回溯，会出现应该能到达的位置被访问
2.多起点
struct pp{
int x;
int y;
int step;
int vis[10][10];
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int m;
int n;
int vis[10][10];
int f=0;
bool exist(vector<vector<char>>& board, string word) {
m=board.size();
n=board[0].size();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j]==word[0]){
//memset(vis,0,sizeof(vis));
//起点位置vis设置为1之后，也会影响别的起点的dfs,所以要回溯
vis[i][j]=1;
dfs(board,word,i,j,1);
vis[i][j]=0;
if(f==1){
return true;
}
}
}
}
return false;
}
void dfs(vector<vector<char>>& board,string word,int x,int y,int step){
// cout<<" dfs "<<x<<" "<<y<<" step "<<step<<endl;
if(step==word.size()){
f=1;
return ;
}
//vis[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&board[nx][ny]==word[step]&&vis[nx][ny]!=1){
// cout<<board[nx][ny]<<" step "<<step<<endl;
vis[nx][ny]=1;
dfs(board,word,nx,ny,step+1);
vis[nx][ny]=0;
}
}
}