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

Предпосылки

Прежде чем мы начнем разбираться с лабиринтами, давайте поговорим о самой доске. На 2-й доске есть нули и единицы: «ноль» представляет свободную ячейку (можно пройти), а «единица» представляет заблокированную ячейку, через которую нельзя пройти. Доска представлена ​​массивом массивов: каждый подмассив — это строка на доске, а каждый элемент — это ячейка. Например, доска 3*2 может быть представлена ​​как [[0,1,1],[0,0,0]). В этом случае значение board[0][2] равно «1».

Кроме того, я создал класс, представляющий «точку», которая получает строку и столбец в конструкторе. Сам класс включает в себя несколько функций для получения соседних точек (справа, слева, снизу, сверху и по диагонали). Более того, функция проверки достижимости точки представлена ​​функцией «isValid». Проверяется не только то, находится ли точка в сетке, но и то, равно ли значение точки нулю («доступно»).

Небольшие функции isEqual предназначены для сравнения двух точек путем сравнения их строк и столбцов. Функция «getString» используется для записи пути решения лабиринта. Печать пути в методе «printPath» использует массив путей, который включает точки в строковом формате. Например, напечатанный путь может быть «00»->»10->»11.

Классический лабиринт (четыре направления) с использованием рекурсии

Классический лабиринт, представленный доской с нулями для свободных ячеек и единицами для заблокированных ячеек. В этом примере я использовал рекурсию для поиска доступного пути. Если путь не найден, программа возвращает «undefined».

Чтобы избежать бесконечного цикла в противоположных направлениях (право-лево, верх-низ), я добавил «обнаруженный» объект. После посещения точки в лабиринте я добавил точку к этому объекту карты и в результате точки посещаются не более одного раза.

Проблема может быть, когда доска становится большой и рекурсия в этом случае может привести к ошибке переполнения стека. В этом случае я предлагаю использовать алгоритмы поиска BFS/DFS в качестве решения, и это будет объяснено в следующих параграфах.

Лабиринт с тремя направлениями (вправо, вниз, по диагонали) с использованием BFS и DFS

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

Идеи, лежащие в основе алгоритмов поиска BFS и DFS, очень похожи, но обратите внимание, что в режиме DFS я использую стек и цикл, который берет последнюю точку в каждом цикле. В этом методе я углубляюсь в дерево (вертикальный поиск). Это отличается от алгоритма BFS, который я ищу горизонтально и использую очередь, чтобы брать первую точку в очереди каждый цикл. Поиск DFS иногда может быть неэффективным, если конечная точка является сестрой текущей точки (ожидание завершения перемещения всех потомков точки).

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

Спасибо!