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

AOJ 1046 Ghost Buster!

AOJ C/C++ BFS

問題

Ghost Buster

解法

BFSで解ける。リンレンの双子の問題はバグ埋め込んでなかなかACでなかったけど、今回は一発AC。全探索の実装なれてきたのかな

心臓に悪いコード

int dy[] = {0, -1,0,1,0}, dx[] = {0, 0,-1,0,1};
int gdy[] = {0, 0, 1, 0, 0, 0, 0, 0, -1}, gdx[] = {0, 0, 0, 0, -1, 0, 1, 0, 0};
int H, W;
char field[32][32], pattern[16];

P nexta(int y, int x, int d){
  int ny = y+dy[d], nx = x+dx[d];
  ny = max(0, min(H-1, ny));
  nx = max(0, min(W-1, nx));
  if(field[ny][nx] == '#'){
    ny = y;
    nx = x;
  }
  return MP(ny, nx);
}

P nextb(int y, int x, int c){
  int L = strlen(pattern);
  int ny = y+gdy[pattern[c%L]-'0'], nx = x+gdx[pattern[c%L]-'0'];
  ny = max(0, min(H-1, ny));
  nx = max(0, min(W-1, nx));
  return MP(ny, nx);
}

int main(){
  while(scanf("%d%d", &H, &W) && H+W){
    rep(i, H) scanf("%s", field[i]);
    scanf("%s", pattern);
    int ay, ax, by, bx;
    rep(i, H) rep(j, W){
      if(field[i][j] == 'A'){ ay = i; ax = j;}
      else if(field[i][j] == 'B'){ by = i; bx = j;}
    }

    queue<pair<int, pipi> >q;
    map<pair<pipi, int>, int>m;
    q.push(MP(0, MP(MP(ay, ax), MP( by, bx))));
    m[MP(MP(MP(ay, ax), MP(by, bx)), -1)] = 1;

    while(!q.empty()){
      pair<int, pipi> now = q.front(); q.pop();
      if(now.AY == now.BY && now.AX == now.BX){
    printf("%d %d %d\n", now.F, now.AY, now.AX);
    goto e;
      }

      rep(d, 5){
    P na = nexta(now.AY, now.AX, d);
    P nb = nextb(now.BY, now.BX, now.F);

    if(m.count(MP(MP(na, nb), (now.F%strlen(pattern))))) continue;

    m[MP(MP(na, nb), now.F%strlen(pattern))] = 1;
    q.push(MP(now.F+1, MP(na, nb)));
      }
    }
    puts("impossible");
  e:;
  }
  return 0;
}

幽霊の移動は配列使ってやったのは、いちいち分岐してメイン関数が読みづらくなるのがイヤだったから。結局、サブルーチンにしたけど。せめて0からはじめたり、1~5とかにしてほしかった