Меньше поворотов
Робот-курьер ездит по клетчатому плану города. Прямо он едет быстро, а на каждом повороте останавливается, разворачивается на месте и снова разгоняется. Поэтому ему нужен не самый короткий маршрут, а маршрут с наименьшим числом поворотов, пусть даже длиннее.
Один из тестов — центр Алматы, нарисованный на клетчатой бумаге: улицы из OpenStreetMap повёрнуты на угол городской сетки, клетка — 20 метров, старт у площади Республики, финиш у Зелёного базара.
Вход
В первой строке числа n и m (1 ≤ n, m ≤ 400). Дальше n строк по m символов: . — свободная клетка, # — стена, S — старт, F — финиш (обе клетки свободные, старт и финиш разные). За ход робот переходит в соседнюю свободную клетку по стороне. Поворот — смена направления между двумя соседними ходами; первый ход можно сделать в любую сторону бесплатно.
Выход
Наименьшее число поворотов на пути от S до F или -1, если до финиша не доехать.
Примеры
Пример 1
7 10 S......... .########. ..#######. #..######. ##..#####. ###..####. ####....F.
2
Пример 2
3 5 S..#. .#.#. ...#F
-1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Найдите самый короткий путь обходом в ширину и посчитайте на нём повороты. Сравните с ответом на первом примере.
2Подсказка 2
Чтобы знать, будет ли следующий ход поворотом, мало знать, в какой клетке стоит робот. Что ещё нужно помнить?
3Подсказка 3
В графе, где вершина — пара «клетка, направление», у рёбер всего два веса: 0 и 1. Обычная очередь уже не годится. А дек?
4Идея
Состояние робота — клетка и направление, в котором он смотрит. Из состояния два вида переходов: проехать вперёд в соседнюю клетку (0 поворотов) и повернуться на месте налево или направо (1 поворот). Нужен кратчайший путь в графе с весами 0 и 1, и для него есть приём проще Дейкстры — обход 0-1: в деке вершину, до которой дошли по ребру веса 0, кладут в начало, а по ребру веса 1 — в конец.
5Разбор
Почему дек работает. В обычном обходе в ширину в очереди лежат вершины не больше чем двух соседних слоёв: k в голове, k + 1 в хвосте. Здесь то же самое: ребро веса 1 добавляет вершину слоя k + 1 в хвост, а ребро веса 0 даёт вершину того же слоя k, и ей место в голове, перед всеми k + 1. Дек остаётся отсортированным, и вершины достаются по неубыванию расстояния — ровно то, что делает куча Дейкстры, только без логарифма.
Старт — четыре состояния (S, вверх), (S, вправо), (S, вниз), (S, влево) с нулём поворотов: первое направление бесплатно. Ответ — расстояние первого состояния с клеткой F, которое достали из дека. Разворот на 180° не нужен никогда: два поворота подряд на месте ничего не дают. Эталон обносит план рамкой из стен, чтобы не проверять выход за край.
Почему не работает первая подсказка: в первом примере кратчайший путь — лестница из четырнадцати ходов, на которой девять поворотов. Обход по краю на два хода длиннее, а поворотов на нём два.
5+Решение
6Сложность
Состояний 4nm, из каждого три перехода, каждое попадает в дек не больше двух раз: O(nm). Дейкстра с кучей тоже верна, но медленнее в log раз; на Python для плана 400 × 400 это заметно.
7Типичные ошибки
- Кратчайший путь, а потом подсчёт поворотов. Короткий путь может петлять: это
wrong.py, и его ловит уже первый пример. - Расстояние на клетку вместо расстояния на пару. Если хранить одно число на клетку, то путь, который пришёл в клетку с тем же числом поворотов, но смотрит не туда, затрёт более выгодный.
- Обычная очередь для рёбер 0 и 1. Вершина, найденная по нулевому ребру в хвосте очереди, будет обработана позже вершин с большим расстоянием, и ответ испортится.
- Плата за первый ход. Начальное направление выбирают бесплатно, поэтому стартовых состояний четыре.