[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}|) \]

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

コード

 

AOJ, 数学

Posted by ヤマカサ