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

AOJ 0230 Ninja Climbing

問題

Ninja Climbing

解法

BFSで通った。もしビルの屋上を超えてしまっても屋上につくことはできる

心臓に悪いコード

cpp
int n, b[2][128];

int rec1(int x, int y){
  if(b[x][y+1] == 1) return rec1(x, y+1);
  return y;
}

int rec2(int x, int y){
  if(b[x][y] == 2) return rec2(x, y-1);
  return y;
}

int main(){
  while(scanf("%d", &n) && n){
    rep(i, 2) rep(j, n) scanf("%d", &b[i][j]);

    queue<pii>q;
    q.push(MP(0, MP(0, 0)));
    q.push(MP(1, MP(0, 0)));
    map<pi, int>m;
    m[MP(0, 0)] = 1; m[MP(1, 0)] = 0;

    int res = -1;
    while(!q.empty()){
      pii now = q.front(); q.pop();
      if(b[now.F][now.S.F] == 1) now.S.F = rec1(now.F, now.S.F);
      else if(b[now.F][now.S.F] == 2) now.S.F = rec2(now.F, now.S.F);

      if(now.S.F >= n-1){
    res = now.S.S;
    break;
      }

      rep(i, 3){
    pii next = now;
    next.F = (next.F+1)%2;
    next.S.F += i;
    next.S.S++;
    if(m.count(MP(next.F, next.S.F))) continue;
    m[MP(next.F, next.S.F)] = next.S.S;
    q.push(next);
      }
    }
    if(res < 0) puts("NA");
    else printf("%d\n", res);
  }
  return 0;
}