AOJ0594 - Super Metropolis
問題見たとき幅優先かなと思い,実装したら間違ってて悲しくなったのでブログに残しておきます.
右下と左上方向に移動するときは斜めの道が使えないので,マンハッタン距離の分だけ移動. それ以外は差の絶対値が大きいほうを取る.
コード
// テンプレは省略 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); }