Задача 05-2. Один конь
(Разбор)
Пусть клетки шахматной доски будут вершинами графа. Ребрами соединим такие пары вершин, что конь может попасть из одной в другую за один ход. В этом графе по условию необходимо найти кратчайший путь между двумя заданными вершинами. Это можно сделать с помощью поиска в ширину.
Матрица смежности полученного графа будет очень большой. Заметим, что для любой вершины мы можем без труда найти всех ее соседей. Представим себе, что шахматная доска бесконечна во все стороны. Тогда для любой клетки (x,y) существует ровно восемь соседей: (x+2,y+1), (x+2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y+1). Нашу конечную шахматную доску можно представить как часть бесконечной, и при вычислении соседей просто проверять, попадает ли клетка в рамки нашей доски или нет.
Мысленно сотрем из записи координат соседей данной клетки x и y.
Получим: (+2,+1), (+2,-1), (+1,+2), (+1,-2), (-1,+2), (-1,-2),
(-2,+1), (-2,-1). Эти числа показывают смещения координат клеток, соответствующих соседним вершинам,
относительно координат клетки, соседей которой нам необходимо найти.
Если записать эти смещения в два массива: первый - смещение по x, второй -
соответсвующее ему смещение по y, то перебор всех соседей клетки сведется к
циклу от 1 до 8:
const
dx: array [1..8] of integer = (2, 2, 1, 1,-1,-1,-2,-2);
dy: array [1..8] of integer = (1,-1, 2,-2, 2,-2, 1,-1);
{...}
for i := 1 to 8 do
begin
newx:=x+dx[i];
newy:=y+dy[i];
{...}
end
Таким образом, в этой задаче граф вообще не нужно хранить в памяти компьютера. Заметим, что обход этого графа в ширину будет занимать порядка N*N действий, т.е. пропорционально количеству вершин в нем. Дело в том, что на каждом шаге мы рассматриваем не все вершины, а только соседей, которых не более 8.
[an error occurred while processing the directive]