Question

На шахматной доске размером 8 на 8 в клетке s находится король. Определите, за какое минимальное количество ходов король может перейти в клетку f.
По правилам игры в шахматы король может переместиться на любое поле, соседнее с текущим по вертикали, горизонтали или вертикали. Возможность рокировки в данной задаче не предусмотрена.
ответ сделать на языке Pascal

Answer 1

program shkisvf;

uses

crt;

procedure minh(sx, sy, dx, dy: integer);

var

h: integer;

begin

h := 0;

while ((sx <> dx) and (sy <> dy)) do

begin

if (sx < dx) and (sy < dy) then

begin

sx := sx + 1;

sy := sy + 1;

h := h + 1;

end ;

if (sx > dx) and (sy < dy) then

begin

sx := sx - 1;

sy := sy + 1;

h := h + 1;

end ;

if (sx < dx) and (sy > dy) then

begin

sx := sx + 1;

sy := sy - 1;

h := h + 1;

end ;

if (sx > dx) and (sy > dy) then

begin

sx := sx - 1;

sy := sy - 1;

h := h + 1;

end ;

end;

while ((sx <> dx) or (sy <> dy)) do

begin

if sx < dx then

begin

sx := sx + 1;

h := h + 1;

end ;

if sx > dx then

begin

sx := sx - 1;

h := h + 1;

end ;

if sy < dy then

begin

sy := sy + 1;

h := h + 1;

end ;

if sy > dy then

begin

sy := sy - 1;

h := h + 1;

end ;

end;

writeln('Минимальное количество ходов: ', h);

end;

procedure cheb(sx, sy, dx, dy: integer);

var

max, rx, ry: integer;

begin

rx := abs(sx - dx);

ry := abs(sy - dy);

writeln('Минимальное кол-во ходов по Чебышёву:');

if rx > ry then

writeln(rx)

else

writeln(ry);

end;

var

a, b, c, d: integer;

begin

writeln('Введите координаты точки s:');

readln(a, b);

writeln('Введите координаты точки f:');

readln(c, d);

if ((a < 1) or (a > 8) or (b < 1) or (b > 8) or (c < 1) or (c > 8) or (d < 1) or (d > 8)) then

writeln('Ошибка! Проверьте правильность введённых данных! Закрытие программы... ')

else

minh(a, b, c, d);

cheb(a, b, c, d);

readln;

end.

Answer 2

Наши действия

Для того, чтобы решить задачу, нам не требуется делать какие-то сложные переборы в поисках кратчайшего пути. Так как на поле у нас нет никаких препятствий, нам достаточно рассчитать расстояние между клетками поля. Это и будет ответом.

Как рассчитать расстояние

Для этого используются метрики.

Мне тут давеча сказали, что это слово пугает детей и вводит их в паническое состояние.

¯\_(ツ)_/¯  Не понимаю, чего там такого пугающего)

На самом деле, тут всё просто, так что забудем про страшные слова и посмотрим, как можно вычислять расстояния.

Для примера возьмём плоскость, на которой нам достаточно 2-х координат для задания положения точек.

Как посчитать расстояние между точкой А(x0, y0) и B(x1, y1)?

Уроки геометрии учат, что $L = \sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}$. Поздравляю, ты познакомился со своей первой метрикой. Она называется Евклидова метрика. Или Евклидово расстояние - кратчайшее расстояние между двумя точками пространства.

А теперь представим, что ты оказался в центре города. И тебе надо узнать, как много нужно пройти от твоего местоположения до гостиницы. Путь это будут всё те же точки A и B.

Мы уже могли бы рассчитать Евклидову метрику. Однако она нам мало чем поможет: мы ведь не можем ходить насквозь домов. Придётся обходить. А значит, и расстояние увеличится.

Для такой ситуации подходит Манхэттенская метрика или по-другому Расстояние городских кварталов.

Рассчитывается она тоже просто $L = |x_1 - x_0| + |y_1 - y_0|$. То есть просто сумма расстояний по x и по y. Если ходить по улицам, не через дворы, то нам не важно, сколько раз мы будем поворачивать. Мы пройдем столько же, сколько прошли бы сначала по x, а потом по y.

Помимо этих двух метрик, есть ещё метрика Чебышёва.

Она рассчитывается как $L = \max(|x_1 - x_0| , |y_1 - y_0|)$. То есть вычисляются расстояния по координатам, и выбирается максимальное из них.

Забавно, но одно из объяснений этой метрики звучит как "Минимальное количество ходов, которое требуется совершить королю из клетки A в клетку B".

Ниже я привел картинку, на которой можно увидеть, почему это работает.

Итак, решено. Будем рассчитывать искомое расстояние по методу Чебышёва.

Код

• Program king;
• Var
• x0, y0, x1, y1: integer;
• Begin
• Writeln('Введите координаты точки s:');
• Readln(x0, y0);
• Writeln('Введите координаты точки f:');
• Readln(x1, y1);
• If ((a < 1) or (a > 8) or (b < 1) or (b > 8) or (c < 1) or (c > 8) or (d < 1) or (d > 8)) then
• Writeln('Ошибка! Проверьте правильность введённых данных! Закрытие программы... ')
• Else
• WriteLn(Max(Abs(x1 - x0), Abs(y1 - y0)));

• Readln;
• End.