読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

Problem E: Mirror Cave

ICPC]タグを新規作成しようかと迷ったけど、AOJにした。
コメントがバグりました。誰か助けて

Problem E: Mirror Cave

Problem E : http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2153
ICPC/OBOGの会の模擬国内予選のE問題です。
時間内には解けず、後からチャレンジしてバグがわからないまま終わった気がする。
思い出したので再トライしてみた。



RinとLenの位置を1つの状態とする。
幅優先探索(BFS)しながら、一度生成された状態から再度探索しないようにメモ化。
この前の人材獲得作戦の試験問題と難易度は対して変わらない。

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

#define N 64

char Rin[N][N],Len[N][N];
char memo[N][N][N][N];
int W,H,xr,xl,yl,yr;
const int dx[] = {0,1,0,-1};
const int dy[] = {-1,0,1,0};

int main()
{	// LenRin
	while(cin>>W>>H,W||H){
		cin.ignore();
		memset(Rin,'#',sizeof(Rin));
		memset(Len,'#',sizeof(Len));
		memset(memo,0,sizeof(memo));
		for(int i=0;i<H;i++)scanf("%s %s",Len[i],Rin[i]);
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(Len[i][j]=='L')
					xl=j,yl=i;
				if(Rin[i][j]=='R')
					xr=j,yr=i;
			}
		}
		memo[yl][xl][yr][xr] = 1;
		queue<pair<int,int> > rin,len;
		rin.push(make_pair(xr,yr));
		len.push(make_pair(xl,yl));
		int flag = 0;
		while(!rin.empty() && !flag){
			xr = rin.front().first;
			yr = rin.front().second;
			xl = len.front().first;
			yl = len.front().second;
			
			rin.pop(); len.pop();
			
			for(int k=0;k<4;k++){
				int txR = xr + dx[k];
				int tyR = yr + dy[k];
				int txL = xl + dx[k]*-1;
				int tyL = yl + dy[k];
				if( txR<0 || tyR<0 || txR>=W || tyR>=H || Rin[tyR][txR]=='#')
					txR = xr, tyR = yr;
				if( txL<0 || tyL<0 || txL>=W || tyL>=H || Len[tyL][txL]=='#')
					txL = xl, tyL = yl;
				if( memo[tyL][txL][tyR][txR]==1)continue;
				if( Rin[tyR][txR]=='%' && Len[tyL][txL]=='%'){
					flag=1;
					break;
				}
				if( Rin[tyR][txR]=='%' || Len[tyL][txL]=='%')
					continue;
				
				memo[tyL][txL][tyR][txR] = 1;
				
				rin.push(make_pair(txR,tyR));
				len.push(make_pair(txL,tyL));
			}
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}