[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; }
ディスカッション
コメント一覧
まだ、コメントがありません