AOJ 2153 Mirror Cave

問題

(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153)。

解法

BFSで解く。今まで通った場所を記憶するのにmapを使うとメモリが足りなくなる。

コード

int W, H, used[52][52][52][52];
int dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0};
char len[52][52], rin[52][52];

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 main(){
  while(scanf("%d%d", &W, &H) && W){
    rep(i, H) scanf("%s%s", len[i], rin[i]);

    int ly, lx, ry, rx;
    rep(i, H) rep(j, W){
      if(len[i][j] == 'L'){ ly = i, lx = j; len[i][j] = '.';}
      if(rin[i][j] == 'R'){ ry = i, rx = j; rin[i][j] = '.';}
    }

    memset(used, 0, sizeof(used));
    queue<P>q;
    q.push(P(ly, lx, ry, rx));
    used[ly][lx][ry][rx] = 1;

    while(!q.empty()){
      P now = q.front(); q.pop();
      rep(d, 4){
    int nly, nlx, nry, nrx;
    if(d%2){
      nly = now.ly + dy[d], nlx = now.lx;
      if(nly < 0 || nly >= H || len[nly][nlx] == '#') nly = now.ly; 
      nry = now.ry + dy[d], nrx = now.rx;
      if(nry < 0 || nry >= H || rin[nry][nrx] == '#') nry = now.ry; 
    }else{
      nly = now.ly, nlx = now.lx + dx[d];
      if(nlx < 0 || nlx >= W || len[nly][nlx] == '#') nlx = now.lx;       
      nry = now.ry, nrx = now.rx + -1*dx[d];
      if(nrx < 0 || nrx >= W || rin[nry][nrx] == '#') nrx = now.rx;
    }

    if(len[nly][nlx] == '%' && rin[nry][nrx] == '%'){
      puts("Yes"); goto e;
    }
    if(len[nly][nlx] == '%' || rin[nry][nrx] == '%') continue;
       
    if(used[nly][nlx][nry][nrx] != 0) continue;
    q.push(P(nly, nlx, nry, nrx));
    used[nly][nlx][nry][nrx] = 1;
      }
    }
    puts("No");
  e:;

  }
  return 0;
}