Как я могу выбрать структуру данных для данного лабиринта?

Question

У меня проблема с лабиринтом, как показано на рисунке ниже.

Вы можете рассматривать это как матрицу 6x6, а цель - найти выход для определенного цветного блока. Основываясь на проблемах с лабиринтами, которые я просматривал, я думаю, что применение bfs может быть хорошей идеей вместо использования dfs. Однако я смущен тем, как я могу реализовать дерево, которое может содержать более двух узлов. Есть ли какая-либо другая структура данных, которую я мог бы использовать вместо дерева? Может, граф? Кроме того, многие вопросы просят применить bfs или dfs для решения проблемы лабиринта, но я никогда не видел случая, который бы применял алгоритм поиска A *. Как насчет эффективности и реализации? Если бы вы могли дать мне подсказку о том, что я могу прогрессировать, я буду признателен.

Вот картинка:

Answer 1

Вы можете реализовать «M» способ дерево: http://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html

Answer 2

Примечание по терминологии: график не является заменой для дерева, так как дерево является типом графа. Я думаю, что слово, которое вы ищете, является решеткой.

Я бы реализовал это как матричную форму с узлами X * Y и каждым узлом с четырьмя соединениями (север, юг, восток и запад). Начните с соединений между каждым узлом, затем удалите любые соединения, которые находятся между двумя узлами, где один или оба узла заняты стеной.

Как только у вас есть график, представляющий проблему, вы можете решить, используя что-то вроде Dijkstra's algorithm или various others.