12下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。トラックは東西南北方向の交差点に進入できるが、来た方向へはUターンできない。交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる(赤と青のみ)。交差点に進入できるのは進行方向の信号機が青の場合である。交差点から隣の交差点への移動には一定の時間D分を要するが、渋滞の道路ではさらにd分要する。工事中で通れない道路もある。ダイクストラのアルゴリズムで解けそうですが、この問題の場合、以下のような状態空間を定義すれば、深さ優先探索で解くことができます。あり、メモリも間に合います。masimarock。