%az elso ket parameterben kapott elemet hozzafuzi a harmadik parameterben
%kapott lista ele es az eredmenyt visszaadja a negyedik parameterben.
beszurlista(A,B,L,[A,B|L]).



%vegigmegy az elso parametreben kapott listan es minden elemet berakja a 
%masodik parameterbeli kimeneti listaba, ezek lesznek azok paratlan elemei,
%a paros elemeken pedig 0-k lesznek.
beszurmind([],[]).

beszurmind([A|L],Ki):-
	beszurmind(L,Ki2),
	beszurlista(A,0,Ki2,Ki).
	


%Az elso parameterben kap egy listat, a masodikban pedig egy indexet, 
%leelenorzi, hogy ennek a listanak a 2*az indexedik helyen allo eleme negativ
%-e, vagy ha nem negativ akkor nagyobb e mint a kovetkezo elem, ha igen a ko-
%vetkezo elemhez hozzaad egyet es teljesul.
checklista([B,C|D],1,[B,C|D]):-
	B<0,!.

checklista([B,C|D],1,[B,C2|D]):-
	C<B,
	C2 is C+1,!.

checklista([B,C|D],Sor,[B,C|Uj]):-
		Sor>1,
		Sor2 is Sor-1,
		checklista(D,Sor2,Uj).



%Leelenorzi, hogy az elso ket parameterben kapott koordinatakhoz, a harmadik
%parameterben kapott Y,X par listaban van e kozeli elem (tavolsaguk mindket
%iranyban legfeljebb 1), ha igen meghisul.
checktav(_,_,[]).
checktav(A,B,[C,_|E]):-
	T is abs(A-C),
	T>1,
	checktav(A,B,E),!.

checktav(A,B,[_,D|E]):-
	T is abs(B-D),
	T>1,
	checktav(A,B,E),!.



%leelenorzi, hogy a parameterben kapott listaban a paratlan indexu elemek vagy
%negativak, vagy megegyeznek a kovetkezo elemmel, ha nem meghiusul.
checkmegoldas([]).
checkmegoldas([B,_|D]):-
	B<0,
	checkmegoldas(D).

checkmegoldas([B,C|D]):-
	B=:=C,
	checkmegoldas(D).



%Az elso parameterben kapott Sor, es a masodikban kapott sor listaval (formatum:
%a listaban valtakozva vannak elemek, paratlan index:kivant mennyiseg, paros
%index eddigi mennyiseg), es a harmadikban kapott kordinataparokbol allo fa 
%listaval, valamint az otodik parametreben tarolt eddigi megoldas listaval
%(formatuma: y,x koordinatak felvaltva. a negyedik parameter ugyancsak megol-
%das kimenet, de ez mar n,s,e,w-ek listaja
satrakkeres(S,O,[],[],_):-checkmegoldas(S),checkmegoldas(O).

satrakkeres(S,O,[A-B|Fs],[n|L],E):-
	A1 is A-1,
	A1>0,
	checklista(S,A1,S2),
	checklista(O,B,O2),
	checktav(A1,B,E),
	satrakkeres(S2,O2,Fs,L,[A1,B|E]).

satrakkeres(S,O,[A-B|Fs],[s|L],E):-
	A1 is A+1,
	checklista(S,A1,S2),
	checklista(O,B,O2),
	checktav(A1,B,E),
	satrakkeres(S2,O2,Fs,L,[A1,B|E]).

satrakkeres(S,O,[A-B|Fs],[w|L],E):-
	B1 is B-1,
	B1>0,
	checklista(S,A,S2),
	checklista(O,B1,O2),
	checktav(A,B1,E),
	satrakkeres(S2,O2,Fs,L,[A,B1|E]).

satrakkeres(S,O,[A-B|Fs],[e|L],E):-
	B1 is B+1,
	checklista(S,A,S2),
	checklista(O,B1,O2),
	checktav(A,B1,E),
	satrakkeres(S2,O2,Fs,L,[A,B1|E]).



%a megoldando fuggveny, parameterezese a feladatban megadott.	
satrak(satrak(Ss,Os,Fs),L):-
	beszurmind(Ss,Sor),
	beszurmind(Os,Oszlop),
	satrakkeres(Sor,Oszlop,Fs,L,[]).