题目网址:https://www.luogu.com.cn/problem/P1363
迷宫是无限多块地图拼接而成的,问是否可以在迷宫中走无限远。解决方案是dfs,走出初始地图之后的位置映射到原位置(取模),如果同一个映射位置两次经过的坐标不一样,则表示这个位置可以无限多次经过,就走不出迷宫。
代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define pb(i) push_back(i)
#define ppb(x) pop_back(x)
#define inf 0x3f3f3f3f
#define maxn 1505
int n,m,t,sx,sy;
bool flag=false;
char Map[maxn][maxn];
int vis[maxn][maxn][];//第一维存放是否访问过,第二、三维存放第一次 访问的横纵坐标
int dir[][]={{,},{,-},{-,},{,}};
void dfs(int mx,int my,int x,int y,int dep)
{
if(flag)return;
// pf("%d:%d %d\n",dep,x,y);
if(vis[mx][my][]&&(vis[mx][my][]!=x||vis[mx][my][]!=y))//从(x,y)位置会到达像(x,y+/-m)这样的位置,所以只有一个坐标不同
{//表明映射坐标是第二次到达,可以到达两次则可以到达无穷次
flag=true;
return;
}
//如果已经标志第一次经过该点搜索失败,则下一次从这个点开始深搜同样会失败,跳过
if(vis[mx][my][]&&vis[mx][my][]==x&&vis[mx][my][]==y)return; vis[mx][my][]=;//第一次访问,设置第一次访问的坐标信息
vis[mx][my][]=x;
vis[mx][my][]=y;
int xx,yy,modx,mody;
f(i,,)
{
xx=x+dir[i][];
yy=y+dir[i][]; modx=(xx+(n*))%n;//正向取模,防止模数非正
mody=(yy+(m*))%m;
if(Map[modx][mody])
{
dfs(modx,mody,xx,yy,++dep);
}
}
}
char c;
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%d%d",&n,&m)!=EOF)
{
mem(Map,);
f(i,,n-)
{
f(j,,m-)
{
scanf(" %c",&c);
if(c=='.')Map[i][j]=;
if(c=='S')
{
Map[i][j]=;
sx=i;
sy=j;
}
} }
flag=false;
mem(vis,);
dfs(sx,sy,sx,sy,);
if(flag)pf("Yes\n");
else pf("No\n");
} }