Царь Леонид ездит на тракторе по прямоугольному клетчатому полю размером H × W. Трактор у Леонида модели «только вперёд» и не имеет руля. Когда трактор всё-таки нужно повернуть, то на помощь Леониду приходят спартанцы — они поднимают трактор и

8 октября 2025
Высшая математика

Условие:

Царь Леонид ездит на тракторе по прямоугольному клетчатому полю размером H × W. Трактор у Леонида модели «только вперёд» и не имеет руля. Когда трактор всё-таки нужно повернуть, то на помощь Леониду приходят спартанцы — они поднимают трактор и поворачивают его в одном из 8 направлений (по вертикали, горизонтали или двум диагоналям).

Местостность в окрестностях Спарты каменистая и некоторые клетки непроходимы даже на тракторе. Царь Леонид хочет торжественно проехать из одной точки поля в другую, сделав при этом наименьшее количество поворотов (силы спартанцев надо беречь для боя с Ксерксом). Изначально трактор лежит в начальной точке вверх колесами, чтобы его направить куда-либо нужно привлечь спартанцев. Направление трактора в конечной точке не имеет значения.

Формат ввода
В первой строке входного файла заданы целые числа H, W (1 ≤ H, W ≤ 1000) — высота и ширина поля.

В последующих H строках задано поле, блокированные клетки обозначены латинскими буквами "X", а свободные — точками.

После поля следует строка с двумя целыми числами sx, sy (1 ≤ sx ≤ W, 1 ≤ sy ≤ H) — координаты стартового положения трактора.

Последней строкой идут два целых числа tx, ty (1 ≤ tx ≤ W, 1 ≤ ty ≤ H) — координаты конечного положения трактора.

Координаты отсчитываются от нижнего левого угла поля. Стартовое положение не совпадает с конечным. Стартовая и конечная клетки не являются заблокированными.

Формат вывода
Если пути не существует — выведите одно число -1. Иначе выведите единственное натуральное число — минимальное количество поворотов, которые спартанцы должны будут сделать по пути к конечной клетке.

Код должен использовать bfs. Изначальный поворот (в начале движения из стартовой точки) не учитывается. Пример теста:
Ввод:
5 7
XX....X
X.XXX..
..XXX.X
X.X...X
....XXX
1 1
6 5

Вывод: 3.

Решение:

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

Шаг 1: Понимание задачи

У нас есть прямоугольное поле размером H × W, где некоторые клетки заблокированы. Трактор может двигаться в 8 направлениях (вверх, вниз, влево, вправо и по диагоналям). Мы должны найти путь от стартовой позиции до целевой с минимальным количеством поворотов.

Шаг 2: Подготовка данных

1. Чтение входных данных: Мы считываем размеры поля, само поле, стартовые и целевые координаты.
2. Преобразование координат: Поскольку координаты в задаче начинаются с 1 и отсчитываются от нижнего левого угла, нам нужно будет преобразовать их для удобства работы с массивами.

Шаг 3: Определение направлений

Мы определим 8 направлений движения:
- Вверх: (0, 1)
- Вниз: (0, -1)
- Влево: (-1, 0)
- Вправо: (1, 0)
- Вверх-влево: (-1, 1)
- Вверх-вправо: (1, 1)
- Вниз-влево: (-1, -1)
- Вниз-вправо: (1, -1)

Шаг 4: Реализация BFS

1. Инициализация очереди: Начнем с начальной позиции и всех возможных направлений.
2. Посещение клеток: Для каждой клетки будем проверять, можем ли мы двигаться в заданном направлении, и если можем, добавляем новую позицию в очередь.
3. Подсчет поворотов: Если направление изменяется, увеличиваем счетчик поворотов.

Шаг 5: Код

Вот пример реализации на Python:

Теперь мы можем протестировать программу на предоставленном примере. Вводим данные и проверяем, что вывод соответствует ожидаемому результату. Таким образом, мы реализовали алгоритм BFS для нахождения минимального количества поворотов трактора на клетчатом поле. Если путь существует, программа выведет минимальное количество поворотов, иначе -1.