Project Euler - Problem 82 -

40 x 40のマスを左から右端まで行くときの最小コストを求める, 最短経路を求める問題の一種.
ただし, マスは左から右か上下にしか移動できない.

答えの確認はまだなので, 考えた手順のメモだけ.

右から左に進めればよいから,縦の列ごとに最短経路を求めて行けばよいはず.

つまり,まず1列目の各マスへの最短経路を求め,そこから2列目のマスへの最短経路を求め,...,
そこから右端の列の各マスへの最短経路を求める.

すでに最短経路が決定したマスの集合をXとし,スタートのマスをX0とする.X0は1列目の全てのマスと隣り合っているとする.

1. 列Lが空になるまで繰り返す
  2. Xからのコストが最小になるマスMをLから取り出す
  3. MのコストをXからのコストに更新する
  4. XへMを加える

これを,処理すべき列Lがなくなるまで繰り返す.

k列目まで確定していてXの要素へは最短経路が決まっているとき,
k+1列目のマスで,Xからのコストが最小になるマスMを選べば最短経路になっている.

Mへ行く経路はk列目のマスかMの上下からしかない.k列目のマスからMへのコストが最小なら,上下のマスへk列目のマスから行ってからMへ移動するよりもコストは小さい.