Поиск выхода из лабиринта

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так — дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, точка входа — [row, column] — как координаты в лабиринте.

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

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

Если выхода из лабиринта нет, то нужно вернуть -1.

Решение задачи

Рекурсия

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

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

Путь воды

Поэтому предлагаю попробовать другой вариант. Я называю его «путь воды».

Представьте себе, что на каждой итерации вода распространяется во все стороны по лабиринту на одну клетку от точки входа. Нам нужно запоминать новые, поглощенные водой клетки, и продолжать итерации пока вода не достигнет выхода, либо не упрется в стенку. Ответом задачи будет число итераций пройденных водой до точки выхода.

Реализация на TS (JS)

Написать комментарий

Мало букафф? Читайте есчо !

Задача: подсчитать варианты размена монет

Август 11, 2023 г.

Снова классика задач на перебор вариантов - есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала - не ...

Читать

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать

 

Комментарии к «Поиск выхода из лабиринта»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: