Codeforces Gym 100187 E. Two Labyrinths(이중 그림 BFS에서 공통 최단 루트 찾기)

E. Two Labyrinths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
A labyrinth is the rectangular grid, each of the cells of which is either free or wall, and it's possible to move only between free cells sharing a side.
Constantine and Mike are the world leaders of composing the labyrinths. Each of them has just composed one labyrinth of sizen × m, and now they are blaming each other for the plagiarism. They consider that the plagiarism takes place if there exists such a path from the upper-left cell to the lower-right cell that is the shortest for both labyrinths. Resolve their conflict and say if the plagiarism took place.
Input
In the first line two integers n and m (1 ≤ n, m ≤ 500) are written — the height and the width of the labyrinths.
In the next n lines the labyrinth composed by Constantine is written. Each of thesen lines consists of m characters. Each character is equal either to «#», which denotes a wall, or to «.», which denotes a free cell.
The next line is empty, and in the next n lines the labyrinth composed by Mike is written in the same format. It is guaranteed that the upper-left and the lower-right cells of both labyrinths are free.
Output
Output «YES» if there exists such a path from the upper-left to the lower-right cell that is the shortest for both labyrinths. Otherwise output «NO».
Sample test(s)
Input

3 5
.....
.#.#.
.....
  

.....
#.#.#
.....

Output

NO

Input

3 5
.....
.#.##
.....
  

.....
##.#.
.....

Output
YES
제목: 두 개의 그림을 주고 두 개의 그림이 (0,0)에서 (n-1,m-1)까지의 가장 짧은 경로가 같냐고 묻는다. 세 번째 BFS로 첫 번째 그림의 가장 짧은 경로를 찾고, 두 번째 그림의 가장 짧은 경로를 찾고, 세 번째 그림의 가장 짧은 경로가 같은지 확인한다.이 문제는 나로 하여금 세심함이 얼마나 중요한지 알게 했다. WA는 10번을 썼는데 같은 그룹의 데이터에서 바보같이 한 시간 반을 잘못 찾았고 자세를 몇 번 바꾸었다. 마지막에 표기된 그룹의 크기가 틀렸다는 것을 발견했다. 바로 그룹을 열 때 한 개의 5, 한 개의 5, 한 개의 5를 적게 눌렀다. 그때 찾은 것은 벽에 부딪히고 싶었다.찾아내니까 피를 토할 것 같아. 아아아아...
ac 코드:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#define MAXN 1010000
#define LL long long
#define ll __int64
#include<iostream>
#include<algorithm>
#define INF 0x7fffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
ll powmod(ll a,LL b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
char map[3][555][555];
int v[3][555][555];//    ，   v[3][555][55]
int vis[555][555];
int cnt[3];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m;
int bz;
struct s
{
	int x,y,step;
};
int check(int kk,int xx,int yy)
{
	if(xx<0||xx>=n||yy<0||yy>=m)
	return 0;
	if(v[kk][xx][yy]||map[kk][xx][yy]=='#')
	return 0;
	return 1;
}
queue<s>q;
void bfs(int k)
{
	while(!q.empty())
	q.pop();
	s a,b;
	a.x=0;a.y=0;a.step=0;
	v[k][0][0]=1;
	q.push(a);
	while(!q.empty())
	{
		a=q.front();
		q.pop();
		if(a.x==n-1&&a.y==m-1&&a.step<cnt[k])
		{
			cnt[k]=a.step;
			continue;
		}
		for(int i=0;i<4;i++)
		{
			b.x=a.x+dir[i][0];
			b.y=a.y+dir[i][1];
			if(check(k,b.x,b.y))
			{
				b.step=a.step+1;
				v[k][b.x][b.y]=1;
				//printf("debug
");
				q.push(b);
			}
		}
	}
}
void bbfs()
{
	while(!q.empty())
	q.pop();
	s a,b;
	a.x=0;a.y=0;a.step=0;
	vis[0][0]=1;
	q.push(a);
	while(!q.empty())
	{
		if(bz)
		break;
		a=q.front();
		q.pop();
		if(a.x==n-1&&a.y==m-1&&a.step==cnt[1])
		{
			bz=1;
			break;
		}
		for(int i=0;i<4;i++)
		{
			b.x=a.x+dir[i][0];
			b.y=a.y+dir[i][1];
			if(b.x>=0&&b.x<n&&b.y>=0&&b.y<m&&!vis[b.x][b.y]&&map[0][b.x][b.y]=='.'&&map[1][b.x][b.y]=='.')
			{
				b.step=a.step+1;
				vis[b.x][b.y]=1;
				q.push(b);
			}
		}
	}
}
int main()
{
	int i;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		mem(map);
		for(i=0;i<n;i++)
		scanf("%s",map[0][i]);
		for(i=0;i<n;i++)
		scanf("%s",map[1][i]);
		mem(v);
		cnt[0]=INF;cnt[1]=INF;
		bfs(0);
		bfs(1);
		//printf("%d %d
",cnt[0],cnt[1]);
		if(cnt[0]!=cnt[1])
		{
			printf("NO
");
			continue;
		}
		bz=0;
		mem(vis);
		bbfs();
		if(bz)
		printf("YES
");
		else
		printf("NO
");
	}
	return 0;
}