voda(Vstup,Reseni):-voda_x(Vstup,s(0,0),[s(0,0)],RX),voda_y(Vstup,s(0,0),[s(0,0)],RY),vyber_kratsi(RX,RY,R),reverse(R,Reseni).

voda_y(vstup(_,Z),s(Z,_),Akumulator,Akumulator):-!.
voda_y(Vstup,Stav,Akumulator,Cesta):-napust_y_pokud_prazdne(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_y(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.
voda_y(Vstup,Stav,Akumulator,Cesta):-prelij_y_do_x(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_y(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.
voda_y(Vstup,Stav,Akumulator,Cesta):-vypust_x(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_y(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.

napust_y_pokud_prazdne(vstup(c(_,Y),_),s(StavX,0),s(StavX,Y)).

prelij_y_do_x(vstup(c(X,_),_),s(StavX,StavY),s(NovyX,NovyY)):-
	StavY \= 0,
	VolnoX is X-StavX,
	(   (StavY =< VolnoX,NovyX is StavX+StavY, NovyY is 0);
	    (NovyX is X, NovyY is StavY-VolnoX)),!.

vypust_x(vstup(c(X,_),_),s(X,StavY),s(0,StavY)):-!.

nebylo(Stav,Akumulator):- \+ member(Stav,Akumulator),!.

voda_x(vstup(_,Z),s(Z,_),Akumulator,Akumulator):-!.
voda_x(Vstup,Stav,Akumulator,Cesta):-napust_x_pokud_prazdne(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_x(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.
voda_x(Vstup,Stav,Akumulator,Cesta):-prelij_x_do_y(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_x(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.
voda_x(Vstup,Stav,Akumulator,Cesta):-vypust_y(Vstup,Stav,NovyStav),nebylo(NovyStav,Akumulator),voda_x(Vstup,NovyStav,[NovyStav|Akumulator],Cesta),!.

napust_x_pokud_prazdne(vstup(c(X,_),_),s(0,StavY),s(X,StavY)):-!.

prelij_x_do_y(vstup(c(_,Y),_),s(StavX,StavY),s(NovyX,NovyY)):-
	StavX \= 0,
	VolnoY is Y-StavY,
	(   (StavX =< VolnoY,NovyY is StavX+StavY, NovyX is 0,!);
	    (StavX > VolnoY,NovyY is Y, NovyX is StavX-VolnoY,!)),!.

vypust_y(vstup(c(_,Y),_),s(StavX,Y),s(StavX,0)):-!.

vyber_kratsi(S,S2,S):-length(S,L1),length(S2,L2), L1 < L2,!.
vyber_kratsi(_,S,S).