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へ移動するよりもコストは小さい.