元の問題

大通りを使わない場合は自明です。

大通りを使う場合、出発地・目的地それぞれ、上下左右どの方向の大通りを使うかを決め打ち、大通り上の地点から大通り上の地点への最短距離を求める問題を4×4回解くことを考えます。

大通り上の地点から大通り上の地点への最短距離

\(K\geq 2\) のとき、大通りのみを使って移動する経路が最短になることが示せます。\(K=1\) のときは大通りを使わないケースに吸収されるので無視して良いです。

2地点が同一大通り上にある場合は自明です。

そうでないとき必ず大通り同士の交差点を通過します。出発地・目的地それぞれ、2方向どちらの交差点を通るか決め打ち、大通り同士の交差点から大通り同士の交差点への最短距離を求める問題を2×2回解くことを考えます。

大通り同士の交差点から大通り同士の交差点への最短距離

自明です。

実装例(C++)