Maze Résoudre en utilisant le graphique

Question

Hey j'étais dans une compétition de programmation locale et ils m'ont posé cette question que je ne pouvais pas faire alors s'il vous plaît aidez-moi sur celui-ci.

Écrivez un programme qui charge à partir d'un fichier de la taille d'un labyrinthe, puis le labyrinthe lui-même. Pour modéliser le labyrinthe, nous utilisons le caractère "S" qui spécifie la cellule de départ, "." qui spécifie la cellule libre, "#" est un mur et "F" est la cellule finale. Écrivez un programme qui trouvera un chemin de la cellule de départ à la cellule finale. Vous pouvez penser que dans le labyrinthe il y a un robot qui obéit aux commandes, donc pour le labyrinthe suivant, le robot devrait recevoir les commandes suivantes: haut, haut, droite, droite, bas, bas.

labyrinthe 1 fichier texte

5 5 
##### 
#...# 
#.#.# 
#S#T# 
##### 

labyrinthe 2 fichier texte

4 5 
#.#.# 
#.#.# 
#S#T# 
##### 

Écrivez votre programme en général (le labyrinthe entrée maximale peut être au plus 200x200).

L'aide serait grandement appréciée. Je suis juste un sophmore montante donc si vous pouviez me fournir le code alors je pourrais le comprendre et ils le font encore par moi-même.

Answer 1

Une façon de trouver un chemin:

1. Avoir une file d'attente de cellules pour vérifier, et un nombre d'étapes pour chaque cellule de là à la destination.
2. Définissez le nombre de cellules de fin à 0 et ajoutez-le à la file d'attente.
3. Alors que la file d'attente n'est pas vide:
   1. Extrait une cellule de la file d'attente.
   2. Pour chaque cellule voisine libre, comparez le nombre de cellules actuelles + 1 au nombre de cellules voisines. Si c'est moins, si la cellule voisine n'a pas encore de compte, définissez le nombre de cellules voisines sur le nombre + 1 de la cellule actuelle, puis ajoutez la cellule voisine à la file d'attente.

Une fois de la file d'attente vide, chaque cellule libre dans le labyrinthe (qui peut être atteint de la destination) aura le nombre d'étapes dans le plus court chemin vers la destination. Si une cellule n'a pas de compte, il n'y a pas de chemin jusqu'à la destination.

Si la cellule de départ a un nombre,

1. Obtenez le nombre de la cellule de départ.
2. Vérifiez chaque cellule voisine pour un nombre de (compte - 1). Il sera être un, et c'est la prochaine étape dans le chemin. Notez la direction de cette cellule, puis récupérez cette cellule et, si ce n'est pas la destination, répétez l'étape 2 avec cette cellule.

Je vais vous laisser le soin de comprendre comment charger le labyrinthe. C'est la partie facile de tout cela.

Answer 2

Le code est trop à écrire ici, mais la façon la plus courante de résoudre les labyrinthes est de partir dans une direction, et à chaque fois que vous tournez à droite, tournez à droite.

Ceci est garanti pour fonctionner tant que le départ et la sortie sont dans l'une des quatre parois environnantes. Pour les labyrinthes qui n'ont pas leur départ et leur sortie le long des murs, c'est un exercice de récursivité.

Voyez ce que vous pouvez trouver avec le code basé sur ce point de départ!

HTH, James

Answer 3

Si vous ne savez pas quoi chercher: http://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm et ce contient beaucoup plus d'informations: http://www.astrolog.org/labyrnth/algrithm.htm