Wie kann ich die Datenstruktur für das gegebene Labyrinth wählen?

Question

Ich habe Labyrinth Problem wie in der folgenden Abbildung gezeigt.

Sie können dies als 6x6 Matrize betrachten und das Ziel ist es, den Ausgang für den spezifischen farbigen Block zu finden. Basierend auf den Labyrinthproblemen, die ich durchgesehen habe, denke ich, dass die Anwendung von bfs eine gute Idee sein könnte, anstatt dfs zu verwenden. Ich bin jedoch verwirrt darüber, wie ich einen Baum implementieren kann, der mehr als zwei Knoten enthalten kann. Gibt es eine andere Datenstruktur, die ich anstelle von Baum verwenden könnte? Vielleicht, Grafik? Außerdem werden viele Fragen gestellt, um bfs oder dfs anzuwenden, um das Labyrinth-Problem zu lösen, aber ich habe noch nie einen Fall gesehen, der den A * -Suchalgorithmus anwenden würde. Was ist mit der Effizienz und Implementierung? Wenn Sie mir einen Hinweis geben könnten, dass ich Fortschritte machen kann, würde ich geschätzt werden. Hier

ist das Bild:

Answer 1

Sie implementieren können einen „M“ Weg Baum: http://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html

Answer 2

Hinweis zur Terminologie: eine grafische Darstellung ist kein Ersatz für einen Baum, weil ein Baum ist eine Art von Grafik. Ich denke, das Wort, nach dem du suchst, ist ein Gitter.

Ich würde dies als ein Matrix-förmiges Gitter mit X * Y Knoten und jedem Knoten mit bis zu vier Verbindungen (Norden, Süden, Osten und Westen) implementieren. Beginnen Sie mit Verbindungen zwischen jedem einzelnen Knoten und entfernen Sie dann alle Verbindungen zwischen zwei Knoten, an denen einer oder beide Knoten von einer Wand belegt sind.

Sobald Sie ein Diagramm haben, das das Problem darstellt, können Sie mit etwas wie Dijkstra's algorithm oder various others lösen.