[P1363] 幻想迷宫

题目链接

---

很好的一道搜索题，应该是利用了离散化的思想我好蒟蒻呀

地图是根据给定的图无限的拼接的。

所以说暴力建图是不可取的。

其实不难看出，在跨越两张图时。我们就可以看做这个点时空穿梭一般。从底下回来了。

所以只用在原图上跑dfs觉可以了。

那怎么判断是否在同一张图内被遍历了呢？

又这么判断同一个点在不同的图中是否被遍历了呢？

我们可以将他最近被遍历的原坐标（在无限的地图中的坐标）记录下来

、

如果一个点在一次被遍历时，如果这个点上一次被遍历到时的原坐标不等于现在的坐标。那么就找到了解

很好的题

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

bool map[1600][1600];

bool found;

int vis[1600][1600][2];

bool used[1600][1600];

int n,m;

int dx[4]={0,0,-1,1};

int dy[4]={-1,1,0,0};

int turn[2]={1,0};

void dfs(int x,int y,int rx,int ry)

{

	if(used[x][y]&&(vis[x][y][0]!=rx||vis[x][y][1]!=ry))

	{

		found=true;

		return ;

	}

	if(used[x][y]&&vis[x][y][0]==rx&&vis[x][y][1]==ry)

		return ;

	used[x][y]=true;

	vis[x][y][0]=rx;

	vis[x][y][1]=ry;

	int x1,y1,x2,y2;

	for(int i=0;i<=3;i++)

	{

		x1=x+dx[i];

		x2=rx+dx[i];

		y1=y+dy[i];

		y2=ry+dy[i];

		if(x1>n)	x1-=n;

		if(x1<1)	x1+=n;

		if(y1>m)	y1-=m;

		if(y1<1)	y1+=m;

		if(map[x1][y1])

			dfs(x1,y1,x2,y2);

		if(found)

			return ;

	}

}

int main()

{

	cin.sync_with_stdio(false);

	char in;

	int begin,end;

	while(cin>>n>>m)

	{

		memset(map,0,sizeof(map));

		memset(vis,0,sizeof(vis));

		memset(used,0,sizeof(used));

		for(int i=1;i<=n;i++)

			for(int j=1;j<=m;j++)

			{

				cin>>in;

				switch(in)

				{

					case 'S':begin=i;end=j;map[i][j]=true;break;

					case '.':map[i][j]=true;break;

					case '#':map[i][j]=false;break;

				}

			}

		dfs(begin,end,begin,end);

		if(found)

			cout<<"Yes"<<endl;

		else

			cout<<"No"<<endl;

		found=false;

	}

}