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

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