Write a program finding a shortest path with a chess king on a chessboard 8x8 where several squares cannot be accessed (by the king). Input is given in this ordering: * Number of obstacles * Coordinates of the obstacles (pairs of numbers 1.. 8) *

8 октября 2025
Программирование

Условие:

Write a program finding a shortest path with a chess king on a chessboard 8x8 where several squares cannot be accessed (by the king).
Input is given in this ordering:
* Number of obstacles
* Coordinates of the obstacles (pairs of numbers 1.. 8)
* Coordinates of the starting square
* Coordinates of the end square.
Number of the obstacles is on a separate line, obstacles are described each on a separate line (i.e., one pair of numbers on a line). On a line the numbers are separated by the space-character.
Output is either -1 (if the king cannot reach the end-square) or the list of coordinates of all the squares of the path, from starting to ending square. If there exist more paths of the same length, print any of them.
Sample input:
1
2 1
1 1
3 3

Appropriate output:
1 1
2 2
3 3

Решение:

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

Шаги решения:

1. Считывание входных данных: Сначала мы считываем количество препятствий, их координаты, а также координаты начальной и конечной клеток.

2. Инициализация доски: Создаем шахматную доску и отмечаем клетки с препятствиями.

3. Определение возможных движений короля: Король может двигаться на одну клетку в любом направлении (всего 8 возможных направлений).

4. Поиск в ширину (BFS): Используем BFS для поиска кратчайшего пути от начальной клетки до конечной. Мы будем хранить текущую клетку и путь, который мы прошли до нее.

5. Проверка условий выхода: Если мы достигли конечной клетки, выводим путь. Если очередь пуста и мы не достигли конечной клетки, выводим -1.

Пример реализации на Python:

1. : Проверяет, находится ли клетка в пределах доски, не является ли она препятствием и не посещена ли она ранее. 2. : Реализует алгоритм поиска в ширину. Она использует очередь для хранения текущих клеток и словарь для отслеживания родительских клеток, чтобы восстановить путь. 3. : Считывает количество препятствий и их координаты, а также начальные и конечные координаты. 4. : Если путь найден, выводит его координаты, иначе выводит -1. Этот алгоритм эффективно находит кратчайший путь для короля на шахматной доске с учетом препятствий.