Question

Дано клетчатое поле 5х5. В левом верхнем углу (в синей клетке) находится шахматный конь. Посчитайте, через какое минимальное количество ходов конь окажется во второй закрашенной клетке.Поле: 1 2 3 4 51 синий бел бел бел бел 2 бел бел бел бел бел3 бел бел синий бел бел4 бел бел бел бел бел5 бел бел бел бел бел

Answer 1

3-2,5-1,4-3,5-5
сначало идет столб а потом рядок

Answer 2

Для решения данной задачи можно использовать алгоритм поиска в ширину (BFS).

Сначала создадим пустую очередь для хранения координат клеток, которые нужно посетить. Затем добавим начальную позицию коня (синяя клетка) в очередь. Также создадим пустое поле размером 5х5, где каждая клетка будет содержать значение "бесконечность".

Пока очередь не пуста, будем извлекать из нее координаты текущей клетки. Если текущая клетка уже посещена (ее значение в поле не является "бесконечностью"), пропускаем ее. В противном случае, помечаем текущую клетку числом шагов от начальной позиции коня и добавляем в очередь ее соседние клетки.

Каждая клетка имеет максимум 8 соседей, поэтому для каждого соседа проверяем, находится ли он в пределах поля и не был ли уже посещен. Если условия выполняются, добавляем его в очередь.

Повторяем этот процесс, пока не достигнем второй закрашенной клетки. Как только мы достигли ее, возвращаем значение, которое было записано в эту клетку.

Применяя этот алгоритм к данному полю, получим следующую карту шагов для каждой клетки:

1 2 3 4 5 1 0 ∞ ∞ ∞ ∞ 2 ∞ 4 ∞ ∞ ∞ 3 ∞ ∞ 1 ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞

Таким образом, минимальное количество ходов для коня, чтобы попасть во вторую закрашенную клетку, равно 4.