Program test;

(*
     П р а в и л а   п р о г р а м м и с т с к о й   и г р ы   "К Л А Д":
    Имеется игровое поле  N x N .  Оно представлено массивом  Pole : array [ 1..N,1..N ] of integer.
 Если элемент массива Pole[i,k] равен нулю, то клетка игрового поля на пересечении  i-той строки 
 и  k-того столбца пустая.  По пустым полям можно ходить.  Если  Pole[i,k]=1, то клетка игрового 
 поля в  i-той строке и  k-том столбце занята каменной стеной.  Такие клетки нельзя пересекать, 
 даже слегка задевать.  В одной из клеток  Pole[i,k]=5.  В этой клетке находится клад.
    Задача игрока -- дойти до клетки, в которой находится клад.   Каждый участник игры пишет 
 процедуру, содержащую алгоритм одного своего хода.  В начале хода игрок располагает такой 
 информацией:
               X, Y -- номер столбца и номер строки, где сейчас он находится;
               Pole -- весь массив тоже доступен для просмотра.
    Процедура игрока должна определять свой ход, задав две величины dX и dY: 
               dX -- направление смещения по горизонтали:
                                 dX = -1 -- есть смещение на запад;
                                 dX =  1 -- есть смещение на восток;
                                 dX =  0 -- нет смещения по горизонтали.
               dY -- направление смещения по вертикали:
                                 dY = -1 -- есть смещение на север;
                                 dY =  1 -- есть смещение на юг;
                                 dY =  0 -- нет смещения по вертикали.
    Таким образом, совершая ход, игрок может передвинуться на одну клетку в одном из восьми 
 направлений (как шахматный король) или остаться на месте.  Если заявленный игроком ход 
 невозможен, то перемещение не происходит.  Ход невозможен, если:
               в результате хода игрок встал бы на занятую стеной клетку;
               или при движении по диагонали игрок задел бы угол клетки, занятой стеной.
    Оценка зависит от времени (числа ходов), затраченного на то, чтобы найти клад.
*)
uses crt;

const N=20; (* Размер поля *)
const kX=4; (* Координата X клада *)
const kY=6; (* Координата Y клада *)
const Nk=100; (* Максимальное количество итераций *)

var
Pole  : array [ 1..N,1..N ] of integer;
X,Y   : integer;
dX,dY : integer;
step  : integer; (* Количество шагов *)
first : integer; (* Если не 1, то процедура OneStep запускается первый раз*)

wayX  : array [ 1..Nk ] of integer; (* Координаты X маршрута *)
wayY  : array [ 1..Nk ] of integer; (* Координаты Y маршрута *)
pos   : integer; (* Номер шага *)


(* Задает поле *)
procedure SetField();
begin
  (* Стены *)
  Pole[5,5]:=1;Pole[5,6]:=1;Pole[5,7]:=1;
  Pole[5,8]:=1;Pole[5,9]:=1;Pole[5,10]:=1;
  Pole[4,5]:=1;Pole[3,5]:=1;Pole[2,5]:=1;
  Pole[2,6]:=1;Pole[2,7]:=1;Pole[2,8]:=1;
  Pole[2,9]:=1;Pole[2,10]:=1;Pole[2,11]:=1;
  Pole[2,12]:=1;Pole[2,13]:=1;Pole[2,14]:=1;
  
  Pole[15,6]:=1;Pole[15,7]:=1;Pole[15,8]:=1;
  Pole[15,9]:=1;Pole[15,10]:=1;Pole[14,5]:=1;
  Pole[13,5]:=1;Pole[12,5]:=1;Pole[12,6]:=1;
  Pole[12,7]:=1;Pole[12,8]:=1;Pole[12,9]:=1;
  Pole[12,10]:=1;Pole[12,11]:=1;Pole[12,12]:=1;
  Pole[12,13]:=1;Pole[12,14]:=1;Pole[12,15]:=1;
  Pole[12,16]:=1;Pole[13,16]:=1;Pole[14,16]:=1;
  Pole[15,16]:=1;Pole[16,16]:=1;Pole[16,16]:=1;

  Pole[9,2]:=1;Pole[9,3]:=1;Pole[9,4]:=1;
  Pole[9,5]:=1;Pole[9,6]:=1;Pole[9,7]:=1;
  Pole[9,8]:=1;Pole[9,9]:=1;Pole[9,10]:=1;
  Pole[9,11]:=1;Pole[9,12]:=1;Pole[9,13]:=1;
  Pole[9,14]:=1;Pole[9,15]:=1;Pole[9,16]:=1;
  Pole[9,17]:=1;Pole[9,18]:=1;Pole[9,19]:=1;
  Pole[9,20]:=1;Pole[8,2]:=1;Pole[15,5]:=1;
  Pole[7,2]:=1;Pole[6,2]:=1;Pole[5,2]:=1;
  Pole[4,2]:=1;Pole[3,2]:=1;Pole[2,2]:=1;

  (* Клад *)
  Pole[kX,kY]:=5;

  (* Игрок *)
  X:=13;
  Y:=6;
end;

(* Вывод поля на экран *)
procedure DrawField();
var i,j : integer;
begin
  for i:=1 to N do
    for j:=1 to N do 
      begin
        gotoxy(i*2,j);
        case Pole[i][j] of 
          0: write('__');
          1: write('SS');
          5: write('');
        end;
      end;
  (* Вывод игрока *)
  gotoxy(X*2,Y);
  write('');
end;

(* Один шаг *)
procedure OneStep();
var
  R       : array [ 1..N,1..N ] of integer; (* Рабочее поле *)
  i,j     : integer;
  Ni      : integer; (* Номер итерации *)
  found   : boolean;
  min     : integer; 
  mDx,mDy : integer; (* перемещения в волновом алгоритме *)
  mstep   : integer;
begin
  if first<>1 then
    begin (* Начало реализации волнового алгоритма *)
      first:=1;
      for i:=1 to N do
        for j:=1 to N do 
          case Pole[i][j] of 
            0: R[i][j]:=254;
            1: R[i][j]:=255;
            5: R[i][j]:=0;
          end;
      R[X][Y]:=253;
      Ni:=0;
      found:=false;
      (* Шагаем *)
      while (Ni<Nk) do
        begin

          (* Построчно просмaтривaем рaбочий мaссив *)
          for i:=1 to N do
            for j:=1 to N do
              if not found then
                begin
                  if R[i][j]=Ni then
                    begin
                      (* Идем влево вверх *)
                      if (R[i-1][j-1]=254) AND (R[i][j-1]=254) AND (R[i-1][j]=254) AND (i-1>0) AND (j-1>0) then R[i-1][j-1]:=Ni+1;
                      (* Идем влево вниз *)
                      if (R[i-1][j+1]=254) AND (R[i][j+1]=254) AND (R[i-1][j]=254) AND (i-1>0) AND (j+1<=N) then R[i-1][j+1]:=Ni+1;
                      (* Идем вправо вверх *)
                      if (R[i+1][j-1]=254) AND (R[i][j-1]=254) AND (R[i+1][j]=254) AND (i+1<=N) AND (j-1>0) then R[i+1][j-1]:=Ni+1;
                      (* Идем вправо вниз *)
                      if (R[i+1][j+1]=254) AND (R[i][j+1]=254) AND (R[i+1][j]=254) AND (i+1<=N) AND (j+1<=N) then R[i+1][j+1]:=Ni+1;
                      (* Идем влево *)
                      if (R[i-1][j]=254) AND (i-1>0) then R[i-1][j]:=Ni+1;
                      (* Идем вправо *)
                      if (R[i+1][j]=254) AND (i+1<=N) then R[i+1][j]:=Ni+1;
                      (* Идем вверх *)
                      if (R[i][j-1]=254) AND (j-1>0) then R[i][j-1]:=Ni+1;
                      (* Идем вниз *)
                      if (R[i][j+1]=254) AND (j+1<=N) then R[i][j+1]:=Ni+1;

                      (* Проверка  достижения конечной точки *)
                      if R[i-1][j-1]=253 then found:=true;
                      if R[i-1][j+1]=253 then found:=true;
                      if R[i+1][j-1]=253 then found:=true;
                      if R[i+1][j+1]=253 then found:=true;
                      if R[i-1][j]=253 then found:=true;
                      if R[i+1][j]=253 then found:=true;
                      if R[i][j-1]=253 then found:=true;
                      if R[i][j+1]=253 then found:=true;
                    end;
                end;
        Ni:=Ni+1;
        end;

       (* Если маршрута не найдено, то ругаемся *)
       if not found then
         begin
           WriteLn('Маршрута не найдено.');
           halt(1);
         end;

       (* Теперь строим путь *)
       i:=X;
       j:=Y;
       mstep:=0;
       min:=255;
       while (R[i][j]<>0) do
         begin
           if (min>R[i][j+1]) AND (j+1<=N) then begin min:=R[i][j+1];mdx:=0;mdy:=1;end;
           if (min>R[i][j-1]) AND (j-1>0) then begin min:=R[i][j-1];mdx:=0;mdy:=-1;end;

           if (min>R[i+1][j+1]) AND (i+1<=N) AND (j+1<=N) then begin min:=R[i+1][j+1];mdx:=1;mdy:=1;end;
           if (min>R[i+1][j+0]) AND (i+1<=N) then begin min:=R[i+1][j+0];mdx:=1;mdy:=0;end;
           if (min>R[i+1][j-1]) AND (i+1<=N) AND (j-1>0) then begin min:=R[i+1][j-1];mdx:=1;mdy:=-1;end;

           if (min>R[i-1][j+1]) AND (i-1>0) AND (j+1<=N) then begin min:=R[i-1][j+1];mdx:=-1;mdy:=1;end;
           if (min>R[i-1][j+0]) AND (i-1>0) then begin min:=R[i-1][j+0];mdx:=-1;mdy:=0;end;
           if (min>R[i-1][j-1]) AND (i-1>0) AND (j-1>0) then begin min:=R[i-1][j-1];mdx:=-1;mdy:=-1;end;

           i:=i+mdx;      
           j:=j+mdy;
           mstep:=mstep+1;
           wayX[mstep]:=mdx;
           wayY[mstep]:=mdy;
         end;
    end; (* Конец реализации волнового алгоритма *)
  pos:=pos+1;
  dX:=wayX[pos];
  dY:=wayY[pos];
end;

begin
  pos:=0;
  first:=0;
  ClrScr;
  SetField;
  DrawField; 

  (* Делаем шаги пока не нашли клад *)
  step:=0;
  while ((X<>kX) or (Y<>kY)) and (step<100)  do
    begin
      DrawField;
      delay(200);
      OneStep;
      X:=X+dX;
      Y:=Y+dY;
      gotoxy(1,22);
      writeln('игрок: ',X,':',Y,' клад: ',kX,':',kY,'    ');
      step:=step+1;
    end;

  WriteLn('Клад найден за ',step,' шагов');

end.