Problem 82 「経路の和:3方向」 †
数字の書かれたマス目を移動して左端から右端へ到達する。
経路上の数字の和が最小になる経路を通った時のその和を答えよ。
詳細はリンク先参照のこと。
解法
一列ごとの動的計画法で片が付きます。
一列ごとの処理が少しわかりづらいので機能ごとに分割してもよかったかもしれません。
データファイルは一段を一つのリストとしてそのリストの集まりという形に手作業で変換してから読み込んでいる。
seed(0):-
between(0,79,_).
min(a,B,B):-!.
min(A,a,A):-!.
min(A,B,A):-A<B,!.
min(_,B,B):-!.
dp_one_col([[R|Rest]],[Rest],[S],[D],U,D):-
!,
min(U,S,M),
D is R+M.
dp_one_col([[R|Rest]|Rows],[Rest|Rows1],[S|Sum],[S2|Sum1],U,S2):-
!,
min(S,U,M1),
S1 is R+M1,
dp_one_col(Rows,Rows1,Sum,Sum1,S1,D),
min(M1,D,M2),
S2 is M2+R.
dp(_,Sum,81):-!,
sort(Sum,[Min|_]),
write(Min).
dp(Rows,Sum,ColP):-
dp_one_col(Rows,Rows1,Sum,Sum1,a,_),
ColP1 is ColP+1,
dp(Rows1,Sum1,ColP1).
main82:-
open('pe82.txt',read,IS),
read_term(IS,Rows,[]),
close(IS),
findall(S,seed(S),Sum),
dp(Rows,Sum,1).
最終更新:2014年03月04日 11:53