[AOJ] No. 0594 超都観光 (Super Metropolis)

問題

方針

東南方向の斜めの道が無ければ、\( 2 \) 点間の最短距離は、

\[ |X_{i} – X_{i – 1}| + |Y_{i} – Y_{i – 1}|\]

となります。

南西方向

観光スポットが南西方向にある場合、東南方向の道を通る必要がないので、最短距離は、

\[ |X_{i} – X_{i – 1}| + |Y_{i} – Y_{i – 1}|\]

となります。つまり、マンハッタン距離ですね。

東南方向

観光スポットが東南方向にある場合、斜めの道を通る方が最適です。斜めの通る道の本数は、\( \min(|X_{i} – X_{i – 1}| , |Y_{i} – Y_{i – 1}|) \) です。斜めに進んだ後は、縦か横の道のみを渡ることになるので、最短距離は、

\[ \max(|X_{i} – X_{i – 1}| , |Y_{i} – Y_{i – 1}|) \]

となります。これは、チェビシェフ距離となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int W, H, N;
    cin >> W >> H >> N;
    ll X[N], Y[N];
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
    }
    ll ans = 0;
    for (int i = 1; i < N; i++) {
        ll dx = X[i] - X[i - 1];
        ll dy = Y[i] - Y[i - 1];
        if (dx * dy >= 0) {
            dx = abs(dx);
            dy = abs(dy);
            ans += max(dx, dy);
        } else {
            ans += abs(dx) + abs(dy);
        }
    }
    cout << ans << "\n";
    return 0;
}