@page { margin: 2cm } p { margin-bottom: 0.25cm; direction: ltr; color: #000000; line-height: 115%; orphans: 2; widows: 2 } p.western { font-family: "Times New Roman", serif; font-size: 12pt; so-language: ru-RU } p.cjk { font-family: "Times New Roman", serif; font-size: 12pt } p.ctl { font-family: "Times New Roman", serif; font-size: 12pt; so-language: ar-SA }

На шахматной доске (8х8) расположены конь и пешка. Требуется написать программу, вычисляющую, за какое минимальное число ходов конь сможет «взять» пешку. Координаты коня и пешки задаются в шахматном формате, то есть строкой из двух символов. Первый символ обозначает столбец (слева направо: a,b,c,d,e,f,g,h), а второй символ строку (снизу вверх: 1,2,3,4,5,6,7,8). Конь перемещается по доске на две клетки по одной координате и на одну клетку по другой.

Формат входных данных

Первая строка входного файла содержит координаты коня. Вторая - координаты пешки.

Формат выходных данных

В выходной файл необходимо вывести значение минимального количества ходов коня.

Пример входных и выходных данных

Kon.in Kon.out a1 b2 4
d4 a1 2

//PascalABC.NET версия 3.4.0.1677 от 17.06.18

//Если программа не запускается, то обновите версию

const

   input_file = 'Kon.in';

   output_file = 'Kon.out';

type

   TCell = class

   public  

       x, y: integer;

       constructor Create(coords: string);

       begin

           coords := coords.Trim().ToLower();

           y := StrToInt(coords[2]);

           x := ord(coords[1]) - ord('a') + 1;

       end;

       constructor Create(i, j: integer);

       begin

           y := j;

           x := i;

       end;

       function IsDeskCell(): boolean;

       begin

           Result := (x > 0) and (y > 0) and (x <= 8) and (y <= 8);

       end;

       class function operator+(a, b: TCell): TCell;

       begin

           Result := new TCell(a.x + b.x, a.y + b.y);  

       end;

       class function operator=(a, b: TCell): boolean;

       begin

           Result := (a.x = b.x) and (a.y = b.y);

       end;

       function ToString: string; override;

       begin

           Result := Format('({0}, {1})', x, y);  

       end;

   end;

procedure PrintAnswer(path: List<TCell>);

begin

   var f := OpenWrite(output_file);

   Writeln(f, path.Count() - 1);

   Println(path.Count() - 1);

   Println(path);

   f.Close();

end;

begin

   var knight_steps := Arr(

   new TCell(1, 2),

   new TCell(2, 1),

   new TCell(2, -1),

   new TCell(1, -2),

   new TCell(-1, -2),

   new TCell(-2, -1),

   new TCell(-2, 1),

   new TCell(-1, 2)

   );

   //    var f := OpenWrite(input_file);

   //    Writeln(f, 'a1');

   //    Writeln(f, 'b2');

   //    f.Close();

   //    Exit;

   var f := OpenRead(input_file);

   var pawn_place: TCell := new TCell(f.ReadlnString());

   var knight_place: TCell := new TCell(f.ReadlnString());

   f.Close();

   var paths := new List<List<TCell>>();

   var occupied_cells := new List<TCell>();

   paths.Add(Seq(knight_place).ToList);

   occupied_cells.Add(knight_place);

   repeat

       var new_paths := new List<List<TCell>>();

       foreach var path in paths do  

       begin

           foreach var step in knight_steps do  

           begin

               var p := new List<TCell>(path);

               var t := p.Last + step;

               if t.IsDeskCell() and not occupied_cells.Contains(t) then begin

                   p.Add(t);

                   new_paths.Add(p);

                   occupied_cells.Add(t);

               end;

               if t = pawn_place then begin

                   PrintAnswer(p);

                   Exit;

               end;

           end;

       end;

       paths := new_paths;

   until (false)

end.