第13回日本情報オリンピック　予選３

2013年12月15日
情報オリンピック日本委員会

解説

二つの交差点間を移動するために通らなければならない道の本数を， 1 番目と 2 番目の観光スポットの間，2 番目と 3 番目の観光スポットの間 ... N-1 番目と N 番目の観光スポットの間について求め，それらを足せば良い．

現在地を交差点 ( X_s, Y_s )，目的地を交差点 ( X_t, Y_t ) とし，X_s と X_t の差を Dist_x, Y_s と Y_t の差を Dist_y とする．以下のような４つのケースに分けて考える．境界にあるケースについては，いずれか１つのみに含めれば良い．

• ケース 1 : 目的地が現在地の南東にある．
• ケース 2 : 目的地が現在地の北東にある．
• ケース 3 : 目的地が現在地の南西にある．
• ケース 4 : 目的地が現在地の北西にある．

ケース 1 : 目的地が現在地の南東にある

斜めの道を使っても意味がないので，単に Dist_x と Dist_y を足せば良い．

ケース 2 : 目的地が現在地の北東にある

Dist_x か Dist_y のいずれかが 0 になるまで斜めの道を使い，その後は縦または横の道を使えば良い．すなわちこのケースでは，Dist_x と Dist_y の和から Dist_x と Dist_y の小さい方を引けば良い．これは，Dist_x と Dist_y の大きい方の値と一致する．

ケース 3 : 目的地が現在地の南西にある

ケース 2 と同様である．

ケース 4 : 目的地が現在地の北西にある

ケース 1 と同様である．