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

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

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

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

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

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

Рекурсия

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

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

Путь воды

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

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

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

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

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

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

GreyCode генератор

Май 3, 2023 г.

Задачи с бинарными последовательностями мне очень нравятся из-за их "эвристичности". Решение часто скрывается в двух шагах, но додуматься не просто. Следующая задача описывается так - нужно сгенерировать n-разрядный "серый код". Если вы не ...

Читать

 

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

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



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