P1363 幻想迷宫
斯德哥尔摩
2018-10-18 23:04:23
[P1363 幻想迷宫](https://www.luogu.org/problemnew/show/P1363)
首先是语文——题目大意：
给出一个$01$迷宫类的地图，按照这个地图来扩展新地图，问是不是可以走无限远。
我们发现，如果可以从点$(x,y)$出发，达到比如$(-x,y)$或者$(x,-y),(-x,-y),(x+m,y+n)[\text{假设宽m高n}]$，就可以从这个点再次达到相同的点。
即可以从$(x,y)$出发，达到$(i,j)$且$|i|\%n==x,|j|\%m==y$。
然后一直这么走下去。
那就搜好了。
开一个三维$vis$数组：第一维记录有无被访问，第二维记录被访问时横坐标，第三维纵坐标。
判断重复到达且横纵坐标不同即可。
应该注意先判什么后判什么。
如果是同一个分矩阵走过去的话自然$tx==vis[x][y][0]$。
此处$x=|tx|\%n$，$y=|ty|\%m$，即映射到中心矩阵的位置，就会被判掉。
而且注意$tx!=vis[x][y][0]$和$ty!=vis[x][y][1]$满足一个即可。
然后就可以愉快滴$DFS$了。
然而数据很大。。。
所以记得剪枝。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 1510
using namespace std;
const int fx[4]={1,-1,0,0};
const int fy[4]={0,0,1,-1};
int n,m,sx,sy;
int vis[MAXN][MAXN][3];
bool flag,map[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void dfs(int x,int y,int nowx,int nowy){
if(flag)return;
if(vis[nowx][nowy][2]&&(vis[nowx][nowy][0]!=x||vis[nowx][nowy][1]!=y)){
flag=true;
return;
}
if(vis[nowx][nowy][2]&&vis[nowx][nowy][0]==x&&vis[nowx][nowy][1]==y)return;
vis[nowx][nowy][0]=x;vis[nowx][nowy][1]=y;vis[nowx][nowy][2]=1;
int u,v;
for(int i=0;i<4;i++){
u=(nowx+fx[i]+n)%n;v=(nowy+fy[i]+m)%m;
if(!u)u=n;if(!v)v=m;
if(map[u][v])dfs(x+fx[i],y+fy[i],u,v);
if(flag)return;
}
}
void work(){
flag=false;
dfs(sx,sy,sx,sy);
if(flag)printf("Yes\n");
else printf("No\n");
}
void init(){
char ch[MAXN];
memset(vis,0,sizeof(vis));
memset(map,false,sizeof(map));
for(int i=1;i<=n;i++){
scanf("%s",ch+1);
for(int j=1;j<=m;j++){
map[i][j]=(ch[j]=='#'?false:true);
if(ch[j]=='S'){sx=i;sy=j;}
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
work();
}
return 0;
}
```