chemin le plus court à travers un labyrinthe

Question

Je travaille sur un projet que je dois traverser un labyrinthe en utilisant la règle de la main gauche et en fonction des intersections du programme vient je dois créer un noeud pour se connecter à un graphique que je vais ensuite déterminer le chemin le plus court. Le but est que le programme parcourt le labyrinthe puis ferme le programme et lit à partir d'un fichier qui contient le graphique et détermine le chemin le plus court vers la fin. ce que j'ai fait c'est que je peux traverser le labyrinthe en utilisant la règle de la main gauche. ce que je pense à faire est de créer un nœud quand je trouve l'intersection et là après chaque mouvement du programme j'augmente le coût de ce chemin par un. sur une note de côté avez-vous besoin d'avoir une matrice d'adjacence lorsque vous utilisez l'algorithme de dijkstra?

Answer 1

Essayez quelque chose comme ça, il devrait fonctionner:

 
0 - create an empty "solution path" stack of location objects. 

1 - if current position is maze exit, return "solution path" stack. 

2 - wall in front? turn left and repeat 2, else continue to 3. 

3 - if current position is at top of "solution path" stack, 
     pop it off of the stack 
     else push it onto the stack 

4 - move forward. 

Lorsque vous vérifiez le haut de la pile pour la position actuelle, vous pourriez avoir besoin de vérifier l'élément juste avant la toute dernière, depuis le dernier sera la position que vous venez de quitter.