Comment puis-je choisir la structure de données pour le labyrinthe donné?

Question

J'ai un problème de labyrinthe comme montré dans l'image ci-dessous.

Vous pouvez considérer cela comme une matrice 6x6 et le but est de trouver la sortie pour le bloc de couleur spécifique. Basé sur les problèmes de labyrinthe que j'ai examinés, je pense que l'application de bfs pourrait être une bonne idée au lieu d'utiliser dfs. Cependant, je suis confus sur la façon dont je peux implémenter un arbre qui peut contenir plus de deux nœuds. Y a-t-il une autre structure de données que je pourrais utiliser à la place de l'arborescence? Peut-être, graphique? En outre, de nombreuses questions sont posées pour appliquer bfs ou dfs pour résoudre un problème de labyrinthe, mais je n'ai jamais vu un cas qui appliquerait un algorithme de recherche A *. Qu'en est-il de l'efficacité et de la mise en œuvre? Si vous pouviez me dire que je pouvais progresser, je serais reconnaissant.

Voici l'image:

Answer 1

Vous pouvez mettre en place un arbre de façon « M »: http://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html

Answer 2

Remarque sur la terminologie: un graphique ne remplace pas un arbre, car un arbre est un type de graphique. Je pense que le mot que vous cherchez est en treillis. J'appliquerais ceci comme un treillis en forme de matrice avec des nœuds X * Y et chaque nœud avec jusqu'à quatre connexions (nord, sud, est et ouest). Commencez avec des connexions entre chaque nœud, puis supprimez toutes les connexions entre deux nœuds où un ou les deux nœuds sont occupés par un mur. Une fois que vous avez un graphique représentant le problème, vous pouvez résoudre à l'aide de Dijkstra's algorithm ou various others.