Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так — дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, точка входа — [row, column] — как координаты в лабиринте.
В задаче могут требовать найти все выходы, найти ближайший выход, или просто определить есть ли вообще выход из данной точки лабиринта.
Конкретизируем условия задачи: пусть требуется найти длину кратчайшего пути до ближайшкего выхода. Выходом считается любая нулевая ячейка на краю лабиринта, исключая тот случай, если вход в лабиринт задан также на краю лабиринта, т.е. выйти через вход нельзя.
Если выхода из лабиринта нет, то нужно вернуть -1.
Решение задачи
Рекурсия
Можно обратиться к разным подходам, например рекурсивный подход выглядел бы примерно так — мы определяем куда мы можем пойти в текущей позиции (изначально это вход в лабиринт), делаем шаг в свободную соседнюю ячейку и опять смотрим куда можно пойти. На каждой итерации мы перебираем все направления и рекурсивно вызываем перебор дальше, а возвращаем лучший (наименьший результат).
Это был бы довольно сложный подход, т.к. в каждом ветвлении нужно помнить уже пройденный путь, для оптимизации кешировать результаты и т.п.
Путь воды
Поэтому предлагаю попробовать другой вариант. Я называю его «путь воды».
Представьте себе, что на каждой итерации вода распространяется во все стороны по лабиринту на одну клетку от точки входа. Нам нужно запоминать новые, поглощенные водой клетки, и продолжать итерации пока вода не достигнет выхода, либо не упрется в стенку. Ответом задачи будет число итераций пройденных водой до точки выхода.
Реализация на TS (JS)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
function nearestExit(maze: number[][], entrance: number[]): number { // в dir запишем направления, куда может распространятся вода // иногда в задачах говорится, что доступно движение по диагонали, // но мы тут ограничимся только 4мя направлениями const dir = [[0,1],[0,-1],[1,0],[-1,0]], R = maze.length, C = maze[0].length // места, откуда вода продолжает свой путь // записаны в массив spread, // а новые клетки будем сохранять в newSpread let spread: number[][] = [entrance], newSpread: number[][]; // точку входа мы сразу же замуровываем, // чтобы вода не могла "течь" обратно maze[entrance[0]][entrance[1]] = 1; let iter = 0; while (spread.length) { newSpread = []; // перебираем источники воды for (const pos of spread) { // если достигли края карты, и это не было входом, // то мы нашли ближайший выход if ((pos[0] == 0 || pos[0] == R - 1 || pos[1] == 0 || pos[1] == C - 1) && !(pos[0] == entrance[0] && pos[1] == entrance[1])) return iter; // вода течет по направлениям заданным в dir for (const d of dir) { const nR = d[0] + pos[0], nC = d[1] + pos[1] // она не может покинуть карту и не может пройти через стенку if (nR < 0 || nC < 0 || nR == R || nC == C || maze[nR][nC]) continue; // новую позицию тут же замуровываем maze[nR][nC] = 1; newSpread.push([nR, nC]); } } // подставляем найденные ячейки в качестве // данных для следующей итерации spread = newSpread iter ++ } // если не нашли выхода return -1 }; |