Problem 81 「経路の和:2方向」 †
コストが最小になる経路移動の問題その1
詳細はリンク先参照のこと。
解法
上の段からの動的計画法で間に合います。
テキストファイルは一段をリストとしてそのリストのリストに手作業で変換してから読み込んでいる。
sumA([],_,[]):-!.
sumA([X|Xs],Sum,[Sum1|Result]):-
!,
Sum1 is Sum+X,
sumA(Xs,Sum1,Result).
min(A,B,A):-A<B,!.
min(_,B,B):-!.
dp_one_row([],[],_,[]):-!.
dp_one_row([E|Row],[S|Sum],L,[Z|Result]):-
!,
min(L,S,M),
Z is E+M,
dp_one_row(Row,Sum,Z,Result).
dp([],Sums):-
!,
reverse(Sums,[Goal|_]),
write([ans,Goal]).
dp([[T|Row]|Rows],[S|Sums]):-
!,
L is T+S,
dp_one_row(Row,Sums,L,Sums1),
dp(Rows,[L|Sums1]).
main81:-
open('pe81.txt',read,IS),
read_term(IS,[Top|Rows],[]),
close(IS),
sumA(Top,0,Top1),
dp(Rows,Top1).
最終更新:2014年03月04日 11:52