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

AOJ0594 - Super Metropolis

AOJ

問題見たとき幅優先かなと思い,実装したら間違ってて悲しくなったのでブログに残しておきます.

AOJ0594

右下と左上方向に移動するときは斜めの道が使えないので,マンハッタン距離の分だけ移動. それ以外は差の絶対値が大きいほうを取る.

コード

// テンプレは省略

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int W, H, N;
  int px, py;
  cin >> W >> H >> N;
  
  // スタート地点
  cin >> px >> py;
  int ans = 0;
  REP(i, N - 1){
    // ゴール地点
    int nx, ny;
    cin >> nx >> ny;
    // 右下と左上に行くときはマンハッタン距離の分だけ移動する
    if (px > nx && py < ny || px < nx && py > ny){
      ans += abs(px - nx) + abs(py - ny);
    } else {
      // 斜めの道を使うときはX,Yそれぞれの差の絶対値が大きいほうを取る
      ans += max(abs(px - nx), abs(py - ny));
    }
    // スタート地点の更新
    px = nx; py = ny;
  }
  print(ans);
  
  return (0);
}