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

AOJ 0223 Stray Twins

問題

Stray Twins

解法

BFS。入力のところで処理の時とy、x座標を逆にあつかっててwa連発。

心臓に悪いコード

int board[51][51], Y, X;
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};

pii nextp(pii now, int i, int d){
  pii next = now;
  next.Y += dy[i] * d;
  next.X += dx[i] * d;
  if(BW(next.Y, Y) && BW(next.X, X) && board[next.Y][next.X] == 0) return next;
  return now;
}
     
int main(){
  while(scanf("%d%d", &X,  &Y) && X+Y){
    int tx, ty, kx, ky;
    scanf("%d%d%d%d", &tx, &ty, &kx, &ky); tx--; ty--; kx--; ky--;
    rep(i, Y) rep(j, X) scanf("%d", &board[i][j]); 

    map<pair<pi,pi>, bool>m; // t k
    queue<pii>tq, kq;
    tq.push(make_pair(ty, tx));
    kq.push(make_pair(ky, kx));
    m[make_pair(make_pair(ty, tx), make_pair(ky, kx))] = 1;
    int res = 1;
    while(!tq.empty()){
      if(res >= 100) break;
      int qsize = (int)tq.size();
      rep(i, qsize){
    pii t = tq.front(); tq.pop();
    pii k = kq.front(); kq.pop();
    rep(j, 4){
      pii nt = nextp(t, j, 1), nk = nextp(k, j, -1);
      pair<pi, pi> next = make_pair(make_pair(nt.Y, nt.X), make_pair(nk.Y, nk.X));
      if(m.count(next) == 1) continue;
      if(nt == nk){
        printf("%d\n", res);
        goto end;
      }
      m[next] = 1;
      tq.push(nt); kq.push(nk);
    }
      }
      res++;

    }
    puts("NA");
  end:;
  }
  return 0;
}

実行時間が0.081s、何歩目かをキューに入れといて、rep(i, qsize)を無くすと 速くなるんかな。