#include <cstdio>
#include <cstring>
using namespace std;
int n,m,sx,sy;
char c1[1505];
int mp[1505][1505],vax[1505][1505],vay[1505][1505],b[1505][1505];
int xx[5]={0,0,1,0,-1},yy[5]={0,-1,0,1,0};
/*
mp数组表示为该迷宫真实的地方是否有墙,
vax和vay是表示当前的x,y 是被站在 哪个坐标的人幻想来过,
b为是否有人幻想来过当前坐标
*/
//实际计算时当然不可能处理“无限”的情况,只要发现“映射到同一个位置”的坐标可以不同,就说明有解。(走到了另一块地图,那么就可以按照同样的方式走到更远的一块地图)。
//(x%n+n)%n x%n 在x为负数时是不相等的!!!! -5 % 3 = -2
bool bfs(int x,int y){//题目说了地图可以无限大(虽然给出了一个地图。。。也就是说x,y可以无限大或无限小, bfs中的for循环也就没有边界
int tx=(x%n+n)%n,ty=(y%m+m)%m;
//printf("%d %d\n",tx,ty);
if(mp[tx][ty])return 0;
if(b[tx][ty])return (vax[tx][ty]!=x||vay[tx][ty]!=y);
vax[tx][ty]=x;vay[tx][ty]=y;b[tx][ty]=1;
for(int i=1;i<=4;i++)
if(bfs(x+xx[i],y+yy[i]))return 1;
return 0;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(mp,0,sizeof(mp));
memset(b,0,sizeof(b));//只需要初始化mp和b数组,至于vax和vay,在b数组初始化后,若有对应的vax和vay会覆盖
for(int i=0;i<=n-1;i++){
scanf("%s",c1);
for(int j=0;j<=m-1;j++)
{
if(c1[j]=='#')mp[i][j]=1;
if(c1[j]=='S')sx=i,sy=j;
}
}
if(bfs(sx,sy))printf("Yes\n");
else printf("No\n");
}
return 0;
}
P1363 幻想迷宫
2019-05-10