Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Автономный транспорт Уровень: Профи

📜 Вторая находка

В заброшенном районе старого мегаполиса ты находишь забытый беспилотник: корпус покрыт пылью, память повреждена, а навигационный модуль работает в аварийном режиме.

В его памяти сохранился фрагмент городской карты в виде сетки. На ней отмечены: A — точка активации робота, B — последняя зафиксированная цель.

Часть кварталов помечена как запрещённые зоны — когда-то там были обрушения, блокировки или опасные участки. Робот не может через них проходить.

Чтобы восстановить систему навигации, тебе нужно вычислить ключевой параметр — минимальное число шагов, за которое робот сможет добраться из A в B, двигаясь только по разрешённым клеткам.

🧠 Немного о технологии

Современные автономные системы не "видят мир целиком" так, как человек. Они представляют пространство в виде математической модели — чаще всего это граф или дискретная сетка.

🔹 Дискретизация пространства

Реальный город — это непрерывное пространство. Но для вычислений его удобно разбить на небольшие участки:

• кварталы,
• ячейки карты,
• зоны проходимости.

Каждая такая ячейка становится узлом графа. Если между двумя соседними ячейками можно переместиться — между ними проводится связь.

🔹 Карта проходимости

Навигационная система формирует так называемую cost-map или карту проходимости:

• свободные зоны — разрешены для движения,
• опасные зоны — запрещены,
• временные препятствия — могут обновляться в реальном времени.

В упрощённой версии этой технологии:

• ". — проходимо,
• "#" — непроходимо.

🔹 Где это применяется

Такая технология лежит в основе:

• автономных автомобилей, которые строят маршрут по дорожной сети,
• складских роботов, двигающихся между стеллажами,
• дронов, учитывающих запрещённые для полёта зоны,
• спасательных роботов, анализирующих карту разрушенного здания.

В реальности системы гораздо сложнее: они учитывают скорость, трафик, энергоэффективность, динамические препятствия.

Но в основе всех этих систем лежит та же фундаментальная задача: поиск кратчайшего пути в дискретной модели пространства.

📌 Задача

Дана прямоугольная сетка размера N × M:

• A — стартовая клетка,
• B — целевая клетка,
• # — препятствие (запрещённая зона),
• . — свободная клетка.

За один шаг робот может перейти в одну из четырёх соседних клеток: вверх, вниз, влево или вправо.

Диагональные перемещения запрещены.

Необходимо определить минимальное число шагов от A до B. Если путь отсутствует — вывести -1.

📥 Формат входных данных

В первой строке заданы два целых числа N и M — размеры сетки.

Далее следуют N строк по M символов — описание карты.

Гарантируется, что на карте ровно одна клетка A и ровно одна клетка B.

Ограничения

• 1 ≤ N, M ≤ 1000
• Используемые символы: A, B, #, .
• Требуемая сложность решения — O(N · M)

📤 Формат выходных данных

Выведите одно целое число:

• минимальное количество шагов от A до B,
• или -1, если добраться невозможно.

📘 Примеры

Пример 1

Входные данные:

5 7
A..#...
.#.#.#.
.#...#.
.###.#.
...#.#B

Выходные данные: 14

Пример 2

Входные данные:

3 4
A###
####
###B

Выходные данные: -1

Пример 3

Входные данные:

4 5
A....
.###.
...#.
.#..B

Выходные данные: 7