※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。




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).