Блог

Главная - Вопросы по программированию - Как создать график из лабиринта

Как создать график из лабиринта

#java #graph #maze #minimum-spanning-tree

#java #График #Лабиринт #минимальное связующее дерево

Вопрос:

Я хотел реализовать некоторые графические и связующие древовидные элементы, которые я изучил на занятиях на этой неделе, поэтому я создал алгоритм генерации лабиринта на основе алгоритма Прима. Теперь я пытаюсь создать алгоритм для эффективного решения лабиринтов. До сих пор я выполнял заливку потоком, которая в конечном итоге решает проблему лабиринта, но очень неэффективна. Сейчас я пытаюсь найти способ преобразовать лабиринт в график, чтобы использовать алгоритм Дейкстры или DFS, но я в тупике. Лабиринт хранится в двоичном массиве, где 1 — стена, а 0 — открытое пространство. Лабиринт всегда начинается с единственного 0 в первой строке и заканчивается единственным нулем в последней строке. Лабиринт сохраняется, как показано ниже.

 static int maze2[][] = {{1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
                        {1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
                        {1, 0, 0, 0, 1, 0, 1, 0, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 1, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 1, 1, 1, 1, 0, 1, 1, 1, 1}};

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

1. Просто сгенерируйте узел графика для каждой ячейки вашей матрицы (фактически только для нулей), соедините каждую пару смежных узлов (т. Е. Обе записи матрицы равны нулю) и найдите путь от начального до конечного узла. Где в этом процессе вы застряли?

2. Лабиринт — это, по сути, график. Просто рассматривайте каждое целое число как узел, а их соседями являются все целые числа на расстоянии 1 пробела от него.

Ответ №1:

Вы не преобразуете лабиринт в график. Вы просто думаете об этом как о графике.

Когда вы пишете свой алгоритм (BFS, DFS и т.д.), Вам нужно только:

  • Способ идентификации пар узел — (строка, столбец) работает нормально, или вы можете использовать одно целое число строка * ШИРИНА столбец.
  • Способ найти смежные узлы — просто проверьте соседние ячейки в матрице.