洛谷 p1363

幻想迷宫

今天又抄了几篇题解,来复习下

题意是有一个无限重复的迷宫,由相同的子迷宫构成,如果可以走无穷远,yes,否则no.

所以一开始想的是如果当前位置x,y距离sx,sy 横坐标大于n或纵坐标大于m即可走无穷远 但其实是错的

正解应该是一个点经过了两次就可以走到无穷远(走两次就可以走无穷次)

#include<bits/stdc++.h> 

#define ll  long long 
using namespace std;
const int maxn = 1500+1;	//开太大会爆内存

int vis[maxn][maxn][3];	//每个点记录它是否被访问过,上次访问的x,y
bool c[maxn][maxn];		//是否可走
int n,m;
int sx,sy;				//出发点
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
bool cg =false;				//如果成功了就不搜索了
void dfs(int x,int y,int lx,int ly)	//x,y是相对于子地图的位置,lx,ly是真实位置
{
	if(cg)	return ;
	if(vis[x][y][0] && (vis[x][y][1]!=lx || vis[x][y][2]!=ly)){			//该点被访问过 且与当前位置不一样 说明走到了两次
		cg = true;
		return;
	}
	vis[x][y][1] = lx,vis[x][y][2]=ly,vis[x][y][0]=1;//更新标记
//	printf("%d %d %d %d
",x,y,lx,ly);
	for(int i=0;i<4;++i)
	{
		int xx = (x+dx[i]+n)%n,yy = (y+dy[i]+m)%m;
		int lxx = lx+dx[i];
		int lyy = ly+dy[i];
		if(c[xx][yy])
			if (vis[xx][yy][1]!=lxx||vis[xx][yy][2]!=lyy||!vis[xx][yy][0])//避免重复走 或走过
				dfs(xx,yy,lxx,lyy);
	}
	
}

int main()
{
	ios::sync_with_stdio(false); 
	char ch;
	while(cin >> n >>m)
	{
		cg = false;
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;++i)
		{
			
			for(int j=0;j<m;++j)
			{
				cin >> ch;
				if(ch == 'S'){
					sx = i;
					sy = j;
					c[i][j] = true;
					
				}
				else if(ch=='.'){
					c[i][j] =true;
				}
				else if (ch=='#')	c[i][j] =false;
			}
		}
	//	cout << c[5][2] << endl;
		dfs(sx,sy,sx,sy);
		if(cg)
			printf("Yes
");
		else
			printf("No
");
	}
	
	return 0;
}

在处理上还是用到了一些技巧吧

lx,ly才表示真正的位置,x,y只是在地图中的位置