program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes, crt, graph
  { you can add units after this };
type pole=array[1..8,1..8]of integer;
     sur=record
       m,n:integer;
     end;

     bunka=record
       parent:sur;

       bolSom,cesta,prekazka:boolean;
     end;
var x,m,n:array[1..8]of integer;
    a:array[1..8]of boolean;
    b:array[2..16]of boolean;
    c:array[-7..7]of boolean;
    q,q2,striedanie,najdene:boolean;
    i,j,velkost,vyska,sirka,prekazky,index,kon,max:integer;
    z,q3,q4:char;
    h:array[1..8,1..8]of integer;
    bludisko:array[1..82,1..82]of bunka;
    //bolSom:array[1..82,1..82]of boolean;
    bunky:array[1..6400]of sur;
    gm,gd:smallint;
    zaciatok,ciel:sur;
procedure skus(i:integer);
var j:integer;
begin
j:=0;
repeat
j:=j+1;
if a[j] and b[i+j] and c[i-j] then
begin
   x[i]:=j;
   a[j]:=false;
   b[i+j]:=false;
   c[i-j]:=false;
   if i<velkost then begin
               skus(i+1);
               if q=false then
               begin
               a[j]:=true;
               b[i+j]:=true;
               c[i-j]:=true;
               end;
               end
          else q:=true;
   end;
until (j=velkost) or q;
end;
procedure generujBludisko(pocet:integer);
var i,j,r1,r2:integer;
begin
//for i:=2 to vyska-1 do
    //for j:=2 to sirka-1 do
        //bludisko[i,j].:=' ';
for i:=1 to vyska do
    for j:=1 to sirka do
        bludisko[i,j].prekazka:=false;
for i:=1 to vyska do
    for j:=1 to sirka do
        bludisko[i,j].bolSom:=false;
for i:=1 to vyska do
    for j:=1 to sirka do
        bludisko[i,j].cesta:=false;
if q3='y' then
begin
for i:=1 to pocet do
    begin
      repeat
            r1:=random(vyska)+1;
            r2:=random(sirka)+1;
      until (bludisko[r1,r2].prekazka=false)
            and
            (((r1<>zaciatok.m) or (r2<>zaciatok.n))
            and
            ((r1<>zaciatok.m+1) or (r2<>zaciatok.n+1))
            and
            ((r1<>zaciatok.m+1) or (r2<>zaciatok.n))
            and
            ((r1<>zaciatok.m+1) or (r2<>zaciatok.n-1))
            and
            ((r1<>zaciatok.m) or (r2<>zaciatok.n-1))
            and
            ((r1<>zaciatok.m-1) or (r2<>zaciatok.n-1))
            and
            ((r1<>zaciatok.m-1) or (r2<>zaciatok.n))
            and
            ((r1<>zaciatok.m-1) or (r2<>zaciatok.n+1))
            and
            ((r1<>zaciatok.m) or (r2<>zaciatok.n+1))
            and
            (((r1<>ciel.m) or (r2<>ciel.n))
            and
            ((r1<>ciel.m+1) or (r2<>ciel.n+1))
            and
            ((r1<>ciel.m+1) or (r2<>ciel.n))
            and
            ((r1<>ciel.m+1) or (r2<>ciel.n-1))
            and
            ((r1<>ciel.m) or (r2<>ciel.n-1))
            and
            ((r1<>ciel.m-1) or (r2<>ciel.n-1))
            and
            ((r1<>ciel.m-1) or (r2<>ciel.n))
            and
            ((r1<>ciel.m-1) or (r2<>ciel.n+1))
            and
            ((r1<>ciel.m) or (r2<>ciel.n+1))));
      bludisko[r1,r2].prekazka:=true;
    end;
end
else
begin
  for i:=1 to pocet do
    begin
      repeat
            r1:=random(vyska)+1;
            r2:=random(sirka)+1;
      until (bludisko[r1,r2].prekazka=false) and (((r1<>1) or (r2<>2)) and ((r1<>2) or (r2<>1)) and ((r1<>2) or (r2<>2)) and ((r1<>1) or (r2<>1)) and ((r1<>vyska-1) or (r2<>sirka-1)) and ((r1<>vyska) or (r2<>sirka-1)) and ((r1<>vyska-1) or (r2<>sirka)) and ((r1<>vyska) or (r2<>sirka)));
      bludisko[r1,r2].prekazka:=true;
    end;
end;
end;
procedure vypisBludiska();
var i,j:integer;
begin
for i:=1 to vyska do
    begin
    for j:=1 to sirka do
        begin
        if (i=zaciatok.m) and (j=zaciatok.n) then write('Z ')
        else if (i=ciel.m) and (j=ciel.n) then write('C ')
        else if bludisko[i,j].cesta=true then write('= ')
        else if bludisko[i,j].bolSom=true then write('O ')
        else if bludisko[i,j].prekazka=true then write('# ')
        else write('- ');
        end;
    writeln;
    end;
end;
procedure vypisBludiskaGraphom();
var  i,j:integer;
begin
if sirka<vyska then max:=GetMaxY div vyska
else max:=GetMaxX div sirka;
 for i:=1 to vyska do
   for j:=1 to sirka do
   begin
   if (i=zaciatok.m) and (j=zaciatok.n) then setfillstyle(1,green)
   else if (i=ciel.m) and (j=ciel.n) then setfillstyle(1,green)
   else
     if bludisko[i,j].cesta=true then
     setfillstyle(1,green) else
     if bludisko[i,j].bolSom=true then
     setfillstyle(1,yellow) else
     if bludisko[i,j].prekazka=true then
     setfillstyle(1,red) else
     setfillstyle(1,white);
     bar((j-1)*max,(i-1)*max,(j)*max,(i)*max);
     if (i=zaciatok.m) and (j=zaciatok.n) then begin setfillstyle(1,black); moveto((j-1)*max+max div 2,(i-1)*max+max div 2); outtext('Z'); end
     else if (i=ciel.m) and (j=ciel.n) then begin setfillstyle(1,black); moveto((j-1)*max+max div 2,(i-1)*max+max div 2); outtext('C'); end
   end;
end;
procedure vykresliCestu(m,n:integer);
begin
if (m=zaciatok.m) and (n=zaciatok.n) then exit;
bludisko[m,n].cesta:=true;
vykresliCestu(bludisko[m,n].parent.m,bludisko[m,n].parent.n);
end;

procedure najdiNajkratsiuCestu(m,n:integer);
begin
if q4='y' then vypisBludiskaGraphom;
if kon<index then exit;
if (m=ciel.m) and (n=ciel.n) then najdene:=true;
if  najdene then begin vykresliCestu(bludisko[m,n].parent.m,bludisko[m,n].parent.n); exit; end;
if kon<index then exit;
if (m+1>=1) and (m+1<=vyska) and (n>=1) and (n<=sirka) and (bludisko[m+1,n].prekazka=false) and (bludisko[m+1,n].bolSom=false) then
begin
kon:=kon+1;
bunky[kon].m:=m+1;
bunky[kon].n:=n;
bludisko[m+1,n].bolSom:=true;
bludisko[m+1,n].parent.m:=m;
bludisko[m+1,n].parent.n:=n;
end;
if (m>=1) and (m<=vyska) and (n+1>=1) and (n+1<=sirka) and (bludisko[m,n+1].prekazka=false) and (bludisko[m,n+1].bolSom=false) then
begin
kon:=kon+1;
bunky[kon].m:=m;
bunky[kon].n:=n+1;
bludisko[m,n+1].bolSom:=true;
bludisko[m,n+1].parent.m:=m;
bludisko[m,n+1].parent.n:=n;
end;
if (m-1>=1) and (m-1<=vyska) and (n>=1) and (n<=sirka) and (bludisko[m-1,n].prekazka=false) and (bludisko[m-1,n].bolSom=false) then
begin
kon:=kon+1;
bunky[kon].m:=m-1;
bunky[kon].n:=n;
bludisko[m-1,n].bolSom:=true;
bludisko[m-1,n].parent.m:=m;
bludisko[m-1,n].parent.n:=n;
end;
if (m>=1) and (m<=vyska) and (n-1>=1) and (n-1<=sirka) and (bludisko[m,n-1].prekazka=false) and (bludisko[m,n-1].bolSom=false) then
begin
kon:=kon+1;
bunky[kon].m:=m;
bunky[kon].n:=n-1;
bludisko[m,n-1].bolSom:=true;
bludisko[m,n-1].parent.m:=m;
bludisko[m,n-1].parent.n:=n;
end;
index:=index+1;
najdiNajkratsiuCestu(bunky[index].m,bunky[index].n);

end;
{
procedure najdiCestu(m,n:integer);
begin

if (m=vyska) and (n=sirka) then najdene:=true;
if (m<1) or (m>vyska) or (n<1) or (n>sirka) or (bludisko[m,n]='#') or (bolSom[m,n]) or najdene then exit;
bolSom[m,n]:=true;
bludisko[m,n]:='O';
if striedanie then
begin striedanie:=false; najdiCestu(m+1,n); najdiCestu(m,n+1);  end
else begin striedanie:=true; najdiCestu(m,n+1); najdiCestu(m+1,n); end;
najdiCestu(m-1,n);
najdiCestu(m,n-1);
if najdene then bludisko[m,n]:='=';
end;
}
procedure vypisPola(a:pole);
var i,j:integer;
begin
for i:=1 to velkost do
    begin
      for j:=1 to velkost do
          write(a[i,j]:3);
      writeln;
    end;
readln();
end;

procedure skacKonom(por,surX,surY:integer);
var k,u,v:integer;
begin
k:=0;
repeat
inc(k);
u:=surX+m[k];
v:=surY+n[k];
if (u>0) and (v>0) and (u<=velkost)  and (v<=velkost) and (h[u,v]=0) then
   begin
        h[u,v]:=por;
        if por<velkost*velkost then
           begin
           skacKonom(por+1,u,v);
           if q2=false then h[u,v]:=0;
           end
        else q2:=true;
   end;
until q2 or (k=8);
end;
procedure initHorse;
var i,j:integer;
begin
m[1]:=2; n[1]:=1;
m[2]:=1; n[2]:=2;
m[3]:=-1; n[3]:=2;
m[4]:=-2; n[4]:=1;
m[5]:=-2; n[5]:=-1;
m[6]:=-1; n[6]:=-2;
m[7]:=1; n[7]:=-2;
m[8]:=2; n[8]:=-1;
for i:=1 to 8 do
    for j:=1 to 8 do
        h[i,j]:=0;
h[1,1]:=1;
end;


procedure menu;
begin
writeln('1. problem 8 dam');
writeln('2. problem jazdca na schovnici');
writeln('3. prechod bludiskom');
writeln('9. koniec');
end;
begin
  randomize;
  repeat
  clrscr;
  menu;
  z:=readkey();
  case z of
  '1':
    begin
      for i:=1 to 8 do a[i]:=true;
      for i:=2 to 16 do b[i]:=true;
      for i:=-7 to 7 do c[i]:=true;
      writeln('zadaj velkost sachovnice');
      readln(velkost);
      skus(1);
      if q then
         for i:=1 to velkost do write(x[i],' ')
      else writeln('riesenie neexistuje');
      writeln;
      writeln('stlac lubovolnu klavesu');
      readln;
      q:=false;
    end;
  '2':begin
           q2:=false;
           initHorse();
           writeln('zadaj velkost sachovnice');
           readln(velkost);
           skacKonom(2,1,1);
           if q2 then vypisPola(h)
           else writeln('reisenie neexistuje');
           end;
  '3': begin
    writeln('zadaj vysku sachovnice');
    readln(vyska);
    writeln('zadaj sirku sachovnice');
    readln(sirka);
    writeln('chcete zadat suradnice zaciatku a ciela?(y/n)');
    writeln('Ak nie, budu suradnice zaciatku vlavo-hore a suradnice ciela vpravo-dole');
    readln(q3);
    if q3='y' then
    begin
    writeln('zadajte suradnice zaciatku');
    readln(zaciatok.m,zaciatok.n);
    writeln('zadajte suradnice ciela');
    readln(ciel.m,ciel.n);
    end
    else
    begin
      zaciatok.m:=1;
      zaciatok.n:=1;
      ciel.m:=vyska;
      ciel.n:=sirka;
    end;
    writeln('zadaj pocet prekazok');
    readln(prekazky);
    writeln('chcete vidiet v realnom case kroky pocitaca?(y/n)');  writeln('pri rozmeroch bludiska nad 30 neodporucam zapinat tuto funkciu z dovodu dlheho trvana behu programu kvoli vykreslovaniu');
    readln(q4);
    najdene:=false;
    //for i:=2 to vyska-1 do

    //for j:=2 to sirka-1 do
        //bolSom[i,j]:=false;
       generujBludisko(prekazky);
       index:=1;
       kon:=1;
       bunky[1].m:=zaciatok.m;
       bunky[1].n:=zaciatok.n;
       bludisko[zaciatok.m,zaciatok.n].bolSom:=true;
       detectgraph(gd,gm);
       initgraph(gd,gm,'');
       najdiNajkratsiuCestu(bunky[1].m,bunky[1].n);

       clrscr;
       vypisBludiska;
       vypisBludiskaGraphom();
       if najdene=false then writeln('cesta neexistuje');
       readln;
       end;
  end;
  until z='9';




end.