vis是一个三维数组
vis[x][y][0]代表第一次搜到原图坐标(x,y)的x"虚"坐标，vis[x][y][1]代表第一次搜到原图坐标(x,y)的y"虚"坐标，vis[x][y][2]代表是否搜过
这样既可以判断什么时候进入了无限走状态，又可以判断是否死循环了(往前走一步又退回一步)
#include<iostream> #include<cstdio> #include<cstring> #define N 1505 using namespace std; int n,m,sx,sy; int map[N][N],vis[N][N][3]; int dirx[5]={0,0,-1,0,1}; int diry[5]={0,-1,0,1,0}; bool flag; void dfs(int x,int y,int posx,int posy) { if(flag) return; if(vis[posx][posy][2]&&(vis[posx][posy][0]!=x||vis[posx][posy][1]!=y)) { flag=true; return; } if(vis[posx][posy][2]&&vis[posx][posy][0]==x&&vis[posx][posy][1]==y) return; //死循环 vis[posx][posy][0]=x, vis[posx][posy][1]=y, vis[posx][posy][2]=1; for(int i=1;i<=4;i++) { int newposx=(posx+dirx[i]+n)%n,newposy=(posy+diry[i]+m)%m; if(map[newposx][newposy]==0) dfs(x+dirx[i],y+diry[i],newposx,newposy); } } int main() { int T; cin>>T; char ch; while(T--) { flag=false; memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); cin>>n>>m; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>ch; if(ch=='#') map[i][j]=1; if(ch=='S') sx=i,sy=j; } } dfs(sx,sy,sx,sy); if(flag) puts("Yes"); else puts("No"); } }转载于:https://www.cnblogs.com/Patrickpwq/articles/9857298.html
