Генератор случайных ациклических лабиринтов с заданной точкой входа и выхода

Опубликовано: 19 Сентября, 2022

Учитывая два целых числа N и M , задача состоит в том, чтобы сгенерировать любой лабиринт размером N * M , содержащий только 0 (представляющий стену) и 1 (представляющий пустое пространство, где можно двигаться) с точкой входа как P0 и точкой выхода P1 , и есть только один путь между любыми двумя подвижными позициями.

Примечание: P0 и P1 будут отмечены как 2 и 3 соответственно, и можно перемещаться по подвижным позициям в 4 направлениях (вверх, вниз, вправо и влево).

Примеры:

Input: N = 5, M = 5, P0 = (0, 0), P1 = (4, 4)
Output: maze = [ [ 2 1 1 1 1 ],
                             [ 1 0 1 0 1 ],
                             [ 1 0 1 0 0 ],
                             [ 1 1 0 1 0 ],
                             [ 0 1 1 1 3 ] ]
Explanation: It is valid because there is no cycle,  
and there is no unreachable walkable position.
Some other options could be 
[ [ 2 1 1 1 1 ],
  [ 1 0 1 0 1 ],
  [ 1 0 1 0 0 ],
  [ 1 1 1 1 0 ],
  [ 0 0 0 1 3 ] ] 
or
[ [ 2 1 1 0 1 ],
  [ 1 0 1 0 1 ],
  [ 1 0 1 0 0 ],
  [ 1 0 1 1 0 ],
  [ 1 0 0 1 3 ] ].
But these are not valid because in the first one there is a cycle in the maze
and in the second one (0, 4) and (1, 4) cannot be reached from the starting point.

Подход: Задача может быть решена на основе следующей идеи:

Use a DFS which starts from the P0 position and moves to any of the neighbours but does not make a cycle and ends at P1. In this way, there will only be 1 path between any two movable positions.

Для реализации идеи выполните следующие шаги:

  • Инициализируйте стек (S) для итеративной DFS, матрица, которая будет возвращена как случайный лабиринт.
  • Вставьте точку входа P0 в стек.
  • Пока S не пуст, повторите следующие шаги:
    • Удалите позицию (скажем, P ) из S и отметьте ее как видимую.
      • Если пометить положение, пригодное для ходьбы, образует цикл, то не включайте его как подвижное положение.
      • В противном случае установите позицию как доступную для ходьбы.
    • Вставьте в стек соседей P , которые не были посещены в случайном порядке.
    • Случайная вставка в стек гарантирует, что генерируемый лабиринт будет случайным.
    • Если какой-либо из соседей совпадает с P1 , то вставьте его сверху, чтобы мы не пропустили эту позицию из-за образования цикла.
  • Отметьте начальное положение P0 (цифрой 2) и конечное положение P1 (цифрой 3).
  • Верните лабиринт.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * M)

  • Поскольку алгоритм в основном представляет собой DFS с большим количеством условий, временная сложность — это временная сложность DFS: O (V + E) (где V — количество вершин, а E — количество ребер).
  • В этом случае количество вершин равно количеству квадратов в матрице: N * M. Каждая «вершина» (квадрат) имеет не более 4 «ребер» (4 смежных квадрата), поэтому E < 4*N*M. Таким образом, O(V+E) будет равно O(5*N*M), т.е. O(N*M).

Вспомогательное пространство: O(N * M)

  • Каждая вспомогательная матрица требует O(N*M) пространства.
  • Внутри стека не может быть больше N*M квадратов, потому что он никогда (в этой реализации) не содержит один и тот же квадрат более одного раза.
  • Сумма всего упомянутого пространства будет O(N*M).

РЕКОМЕНДУЕМЫЕ СТАТЬИ