はやし屋

競技プログラミングのメモ きたない

aoj 2153: Mirror Cave

ボカロだ~

タイピング遅いなあ...

解法は愚直に幅優先やって
00.53 sec 10096 KB 77 lines 1418 bytes
だった

一位の人 00.23 s ってどんな方法でやったのだろうか

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; ++i)

struct P{
  int rx,ry,lx,ly;
  P(int ly, int lx, int ry, int rx):ly(ly),lx(lx),ry(ry),rx(rx) {};
};

int w,h;

bool chk(int y,int x,string s[]){
  return (y >= 0 && x >= 0 && y < h && x < w && s[y][x] != '#');
}

string rin[99] , len[99];

bool used[52][52][52][52];

int rx,ry,lx,ly;

const int dx[] = {0,-1,0,1};
const int dy[] = {-1,0,1,0};

bool bfs(){

  memset(used,false,sizeof(used));
  queue < P > que;
  que.push(P(ly,lx,ry,rx));

  while(!que.empty()){
    P p = que.front();que.pop();
   
    if(used[p.ly][p.lx][p.ry][p.rx])continue;
    used[p.ly][p.lx][p.ry][p.rx] = true;

    if(len[p.ly][p.lx] == '%' && rin[p.ry][p.rx] == '%')return true;
    if(len[p.ly][p.lx] == '%' || rin[p.ry][p.rx] == '%')continue;

    rep(i,4){

      int nrx = p.rx,nry = p.ry,nlx = p.lx,nly = p.ly;

      if(chk(nly+dy[i],nlx+dx[i],len))nly += dy[i],nlx += dx[i];
      if(chk(nry+dy[i],nrx-dx[i],rin))nry += dy[i],nrx -= dx[i];


      if(!used[nly][nlx][nry][nrx])
	que.push(P(nly,nlx,nry,nrx));
    }
  }

  return false;
}

int main(){

  while(cin >> w >> h && (w|h)){

    rep(i,h)cin >> len[i] >> rin[i];
    rep(i,h){
      rep(j,w){
	if(len[i][j] == 'L')ly = i,lx = j;
	if(rin[i][j] == 'R')ry = i,rx = j;
      }
    }

    cout << (bfs() ? "Yes": "No") << endl;

  }
}