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

Мистер Фокс разрабатывает новую компьютерную игру со следующим сюжетом. Есть прямоугольник 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] <> - 1 then     for j := 1 to 8 do       if (x[i] + dx[j] > 0) and (x[i] + dx[j] <= m) then       if (y[i] + dy[j] > 0) and (y[i] + dy[j] <= 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] <> -1 then     writeln(i:2,' - ',x[i],':',y[i],' - ',a[ x[i], y[i] ],' ');      end.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы