Журналист
Ефрем 3 ноября 2019 в 07:57

Мистер Фокс разрабатывает новую компьютерную игру со следующим сюжетом. Есть прямоугольник 7××9, в левом верхнем углу которого стоит шахматный конь. Игрок должен ввести натуральное число N, после чего в одной из клеток прямоугольника появляется клад. Затем игрок должен провести коня (конь ходит по шахматным правилам — буквой Г) из левого верхнего угла в клетку с кладом, сделав не более N ходов. Если ему это удалось, то он выиграл. При этом число N игроку лучше назвать поменьше, так как на него тратятся игровые бонусы.
Сейчас Мистер Фокс задумался над тем, а каким же может быть самое маленькое число N для данного прямоугольника, при котором игрок сможет выиграть. Помогите Мистеру Фоксу.
В качестве ответа выведите одно натуральное число.

6 - минимальное количество ходов, за которое можно добраться до любой клетки.

Программа на паскале:

const
  m = 7;
  n = 9;
  p = n*m;
 
  dx: array [1..8] of integer = (-2, -1, 1, 2, 2, 1, -1, -2);
  dy: array [1..8] of integer = (1, 2, 2, 1, -1, -2, -2, -1);

var
  a: array [1..m, 1..n] of integer;
  x,y: array [1..p] of integer;
  i,j,l: integer;
  t: boolean;
 
 begin
  for i := 1 to p do
    begin
    x[i] := -1;
    y[i] := -1;
    end;
 
  for i := 1 to m do
  for j := 1 to n do
    a[i,j] := -1;
 
  a[1,1] := 0;
  x[1] := 1;
  y[1] := 1;
  l := 1;
 
  for i := 1 to p do
    if x[i] lt;gt; - 1 then
    for j := 1 to 8 do
      if (x[i] + dx[j] gt; 0) and (x[i] + dx[j] lt;= m) then
      if (y[i] + dy[j] gt; 0) and (y[i] + dy[j] lt;= n) then
      if a[ x[i] + dx[j], y[i] + dy[j] ] = -1 then
        begin
        l := l + 1;
        x[l] := x[i] + dx[j];
        y[l] := y[i] + dy[j];
        a[ x[l], y[l] ] := a[ x[i], y[i] ] + 1;
        end;
 
  for i := 1 to p do if x[i] lt;gt; -1 then
    writeln(i:2, - ,x[i],:,y[i], - ,a[ x[i], y[i] ], );
   
 end.

Компьютеры и вычисления
Для комментирования необходимо зарегистрироваться на сайте