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; }