Ящик на складе

Сложная

План склада — сетка floor из символов: - '.' — свободная клетка; - '#' — стена; - 'S' — кладовщик; - 'B' — ящик; - 'T' — место, куда ящик нужно доставить. Кладовщик ходит по свободным клеткам вверх, вниз, влево и вправо (клетки 'S' и 'T' тоже свободные). Сквозь стены и сквозь ящик пройти нельзя. Чтобы сдвинуть ящик, кладовщик встаёт в соседнюю с ним клетку и шагает в его сторону: ящик сдвигается на одну клетку в том же направлении, если там не стена и не край склада. Это один толчок. Верните наименьшее число толчков, за которое ящик окажется на клетке 'T', или -1, если это невозможно. Шаги самого кладовщика не считаются.

Пример 1

floor=[['#', '#', '#', '#', '#'], ['#', 'T', '.', '.', '#'], ['#', '.', 'B', '.', '#'], ['#', '.', '.', 'S', '#'], ['#', '#', '#', '#', '#']] → 2

Кладовщик заходит под ящик и толкает его вверх, затем обходит справа и толкает влево — 2 толчка.

Пример 2

floor=[['#', '#', '#', '#', '#', '#'], ['#', 'T', '.', 'B', 'S', '#'], ['#', '#', '#', '#', '#', '#']] → 2

Коридор узкий, но толкать нужно как раз влево: два толчка подряд.

Пример 3

floor=[['#', '#', '#', '#', '#'], ['#', 'S', 'B', 'T', '#'], ['#', '#', '#', '#', '#']] → 1

Ограничения

1 ≤ len(floor), len(floor[0]) ≤ 20
все строки сетки одной длины
floor[i][j] — один из символов '.', '#', 'S', 'B', 'T'
символы 'S', 'B' и 'T' встречаются ровно по одному разу

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Breadth-First Search Array Matrix Heap (Priority Queue)

Вход

floor=[['#', '#', '#', '#', '#'], ['#', 'T', '.', '.', '#'], ['#', '.', 'B', '.', '#'], ['#', '.', '.', 'S', '#'], ['#', '#', '#', '#', '#']]

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 75 тестов на сервере, включая скрытые.