program NejkratsiCestaKonem1;
{Nalezeni nejkratsi cesty konem po sachovnici z daneho
vychoziho na cilove pole.
Pouzita metoda reseni: prohledavani do sirky.
Sireni vlny rizeno pouze hodnotami na sachovnici.
Nalezeni cesty zpetnym pruchodem podle hodnot pole S.}

const N = 8;
      M = 9;         {velikost strany sachovnice}
      PocetTahu = 8;  {pocet ruznych tahu z jednoho pole}

var S: array[1..N,1..M] of integer;           {sachovnice}
    Tah: array[1..PocetTahu] of
           record d1,d2:integer end;       {mozne tahy kone}
    Start1, Start2: integer; {souradnice vychozi pozice kone}
    Cil1, Cil2: integer;     {souradnice cilove  pozice kone}
    Krok: integer;         {poradove cislo provedaneho tahu}
    Smer: 0..PocetTahu;    {smer pohybu kone - index v Tah}
    i1,i2:integer;          {pozice kone}
    j1,j2: integer;        {nova pozice kone z (i1,i2)}
    x, y: integer;
    f, g:text;

begin  {program}
{inicializace pole tahu konem:}
Tah[1].d1 := 1; Tah[1].d2 := 2;
Tah[2].d1 := 2; Tah[2].d2 := 1;
Tah[3].d1 := 2; Tah[3].d2 := -1;
Tah[4].d1 := 1; Tah[4].d2 := -2;
Tah[5].d1 := -1; Tah[5].d2 := -2;
Tah[6].d1 := -2; Tah[6].d2 := -1;
Tah[7].d1 := -2; Tah[7].d2 := 1;
Tah[8].d1 := -1; Tah[8].d2 := 2;

{inicializace sachovnice:}
assign(f,'.\zadani.txt');
reset(f);
readln(f,start1, start2);
readln(f, cil1, cil2);

for i1:=1 to N do
  for i2:=1 to M do S[i1,i2] := -1;
while not eof(f) do begin readln(f, x, y);  S[x,y] := -2; end;
S[Start1,Start2] := 0;

close(f);

{algoritmus vlny:}
Krok := 1;
while S[Cil1,Cil2] = -1 do     {nemame cestu na cilove pole}
  begin
  for i1:=1 to N do
    for i2:=1 to M do           {zkusime jit z pole (i1,i2)}
      if S[i1,i2] = Krok-1 then
        for Smer:= 1 to PocetTahu do
                                 {zkusime pohyb vsemi smery}
          begin
          j1 := i1 + Tah[Smer].d1;
          j2 := i2 + Tah[Smer].d2;    {nove souradnice kone}
          if (j1>=1) and (j1<=N) and
             (j2>=1) and (j2<=M) then {je uvnitr sachovnice}
            if S[j1,j2] = -1 then  {pole dosud nenavstiveno}
              S[j1,j2] := Krok    {na (j1,j2) dorazila vlna}
          end;
  Krok := Krok+1
  end;

assign(g,'.\tahkun.txt');
rewrite(g);
for  i1:=1 to N do
 begin for i2:=1 to M do begin
   if ((i1=cil1) and (i2=cil2)) then write(g,'c':3)
   else if ((i1=start1) and (i2=start2)) then write(g,'s':3)
        else write (g, S[i1,i2]:3);
        end;
   writeln(g);
 end;



{nalezeni cesty zpetnym pruchodem podle hodnot pole S:}
writeln(g,'Nejkratsi cesta v obracenem poradi:');
write(g,'(', Cil1, ',', Cil2, ')  ');
i1 := Cil1;
i2 := Cil2;
while (i1 <> Start1) or (i2 <> Start2) do
  begin
  Smer := 1;
  repeat
    j1 := i1 + Tah[Smer].d1;
    j2 := i2 + Tah[Smer].d2;    {nove souradnice kone}
    if (j1>=1) and (j1<=N) and (j2>=1) and (j2<=M) then
                                      {je uvnitr sachovnice}
      if S[j1,j2] = S[i1,i2]-1 then
                  {pole (i1,i2) je primo dostupne z (j1,j2)}
        begin
        i1 := j1;
        i2 := j2;
        write(g,'(', i1, ',', i2, ')  ');
        Smer := 0          {uz neni treba jit zadnym smerem}
        end
      else
        Smer := Smer+1     {zkusime jiny smer pohybu}
    else
      Smer := Smer+1       {zkusime jiny smer pohybu}
  until Smer = 0           {uz neni treba jit zadnym smerem}
  end;
writeln(g);
close(g);
end.
