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

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

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

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

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

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

Рекурсия

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

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

Путь воды

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

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

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

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

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

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

Задача о наибольшей сумме монет

Апрель 15, 2023 г.

Решаем задачу № 2218 с leetcode - Maximum Value of K Coins From Piles. В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да - суть именно такая. У нас есть стопки монет, и дано число ...

Читать

 

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

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



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