Ближайший выход из лабиринта

Средняя

Лабиринт задан таблицей grid из m строк и n столбцов: . — свободная клетка, + — стена. Вы стоите в свободной клетке start = [строка, столбец] (нумерация с нуля). За один шаг можно перейти в соседнюю клетку сверху, снизу, слева или справа, если это не стена и она не за пределами таблицы. Выход — любая свободная клетка на краю таблицы, кроме стартовой. Верните наименьшее число шагов до какого-нибудь выхода или -1, если ни до одного выхода не добраться.

Пример 1

grid=[["+", "+", "+", "+"], [".", ".", ".", "+"], ["+", "+", ".", "+"], ["+", "+", ".", "+"]], start=[1, 2] → 2

Выходов два: клетка [1, 0] (два шага влево) и клетка [3, 2] (два шага вниз). До ближайшего — 2 шага.

Пример 2

grid=[[".", ".", "."]], start=[0, 1] → 1

Все клетки на краю, соседняя клетка уже выход.

Пример 3

grid=[["+", "+"], [".", "+"]], start=[1, 0] → -1

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

Ограничения

1 ≤ m, n ≤ 100
Каждая клетка — . или +
start — свободная клетка внутри таблицы

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

Breadth-First Search Array Matrix

Вход

grid=[["+", "+", "+", "+"], [".", ".", ".", "+"], ["+", "+", ".", "+"], ["+", "+", ".", "+"]], start=[1, 2]

Ожидается

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