2153-Mirror Cave
レン可愛いよ。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2153
考え方
リンとレンの位置でBFSする。
片方だけが先にゴールに到着するようなことは無いということに注意する。
実装(C++)
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <vector> #include <iostream> #include <string> using namespace std; #define MEMCLEAR(variable_d) memset(variable_d,0,sizeof(variable_d)) typedef pair<int,int> P;typedef pair<P,P> Q; P LINStart,RENStart,LINEnd,RENEnd; char LIN[52][52],REN[52][52]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; char accessed[52][52][52][52]; bool solve(){ MEMCLEAR(accessed);queue<Q> que; Q res=Q(LINEnd,RENEnd),s=Q(LINStart,RENStart),n;que.push(s); while(!que.empty()){ s=que.front();que.pop(); if(s==res)return true; if(s.first==LINEnd)continue; if(s.second==RENEnd)continue; accessed[s.first.first][s.first.second][s.second.first][s.second.second]=1; for(int i=0;i<4;i++){ n.first=s.first;n.first.first+=dx[i];n.first.second+=dy[i]; if(LIN[n.first.first][n.first.second]=='#')n.first=s.first; n.second=s.second;n.second.first-=dx[i];n.second.second+=dy[i]; if(REN[n.second.first][n.second.second]=='#')n.second=s.second; if(accessed[n.first.first][n.first.second][n.second.first][n.second.second]==0){ que.push(n); accessed[n.first.first][n.first.second][n.second.first][n.second.second]=1; } } } return false; } int main(){ int w,h; for(;(cin>>w>>h),w;){ string in; memset(LIN,'#',sizeof(LIN)); memset(REN,'#',sizeof(REN)); for(int i=0;i<h;i++){ cin>>in; for(int j=0;j<w;j++){ if(in[j]=='L'){ LINStart=P(j+1,i+1);in[j]='.'; }else if(in[j]=='%'){ LINEnd=P(j+1,i+1);in[j]='.'; } LIN[j+1][i+1]=in[j]; } cin>>in; for(int j=0;j<w;j++){ if(in[j]=='R'){ RENStart=P(j+1,i+1);in[j]='.'; }else if(in[j]=='%'){ RENEnd=P(j+1,i+1);in[j]='.'; } REN[j+1][i+1]=in[j]; } } cout<<(solve()?"Yes":"No")<< endl; } return 0; }