LoginSignup
0
0

More than 3 years have passed since last update.

オフラインどう書く第4回参考問題の解

Last updated at Posted at 2019-07-06

問題はこちら->https://qiita.com/Nabetani/items/9c514267214d3917edf2
だいぶ前に解いていたのの入出力を修正しました。力技です。
5x5の交点を数字で表し、道を隣の交点間からなる有向線分に分割してリストに入れ、
通行止めの区域を有向線分に変換してリストから削除し、
残りの線分を入口から出口まで、search/3で終点=始点のしりとりのようにつないでゆきます。
assert/1を使って足し算だけすればメモリ使用量は減りそうですが、
あまり使いたくありませんので、findall/3を使いました。
ideoneでは時間内に全問は解けません。

%swi-Prolog  version 7.4.2
%start.

closed([[]],[]):-!.
closed([],[]):-!.
closed([Lh|Lt],L):-closed(Lt,L1),[F,T]=Lh,append([(F,T),(T,F)],L1,L).

closerout(_,_):-! .
closerout(Input,Street,RL):-
     atom_string(Input1,Input),concat_atom(Out,' ',Input1),
     maplist(atom_codes,Out,List),closed(List,Close),subtract(Street,Close,Street1),
     findall(Res,search(Street1,[97],Res),RL).

search(_,[121|Rout],[121|Rout]):-!.
search(Street,Rout,Res):-
     Rout=[Point|_],member((Point,NTo),Street),not(member(NTo,Rout)),
     subtract(Street,[(Point,NTo),(NTo,Point)],Street1),Rout1=[NTo|Rout],
     search(Street1,Rout1,Res).

start:-data(L),numlist(97,121,Stre),
     findall((A,B),(select(A,Stre,Stre1),select(B,Stre1,_),
     N is A-B,((abs(N,1),(A>B->C=A;C=B),N1 is (C-97) mod 5,N1=\=0);
     abs(N,5))),Street),go(L,Street).

go([],_):-!.
go([I->N|T],Street):-
     closerout(I,Street,RL),length(RL,R),
     (N==R->write("pass ");write("fail ")),writeln(R),go(T,Street).

data(["" -> 8512,
"af" -> 4256,
"xy" -> 4256,
"pq qr rs st di in ns sx" -> 184,
"af pq qr rs st di in ns sx" -> 92,
"bg ch di ij no st" -> 185,
"bc af ch di no kp mr ns ot pu rs" -> 16,
"ab af" -> 0,
"ty xy" -> 0,
"bg ch ej gh lm lq mr ot rs sx" -> 11,
"ty ch hi mn kp mr rs sx" -> 18,
"xy ch hi mn kp mr rs sx" -> 32,
"ch hi mn kp mr rs sx" -> 50,
"ab cd uv wx" -> 621,
"gh mn st lq qr" -> 685,
"fg gl lm mr rs" -> 171]).
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0