parcourir un labyrinthe

Question

voila mon code et jarrive pas à le finir je veux cree une fonction pour parcourir le labyrinthe si vous pouviez me repondre #include #define VRAI 1 #define FAUX 0 void affiche (int T[20][20]); void gauche (int i, int j); void droite (int i, int j); void monter (int i, int j); void descendre (int i, int j); int T[20][20]={ { 0, 0, 0, 0,-1,-1,-1, 0,-1,-1,-1,-1, 0, 0,-1,-1,-1,-1,-1,-1 }, {-1,-1,-1, 0,-1, 0, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0,-1, 0, 0, 0, 0, 0, 0,-1, 0,-1,-1,-1, 0, 0,-1, 0,-1,-1, 0 }, { 0,-1, 0,-1,-1,-1, 0, 0,-1,-1,-1,-1,-1, 0, 0,-1, 0,-1, 0, 0 }, { 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, 0, 0,-1, 0,-1, 0, 0 }, {-1,-1, 0, 0,-1,-1, 0, 0,-1,-1, 0, 0,-1,-1,-1,-1,-1,-1, 0, 0 }, { 0,-1, 0,-1, 0, 0, 0,-1,-1, 0, 0, 0, 0, 0,-1,-1,-1,-1, 0, 0 }, { 0, 0, 0,-1, 0,-1,-1,-1, 0, 0, 0, 0, 0, 0,-1,-1,-1,-1, 0, 0 }, {-1,-1,-1,-1, 0,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1,-1,-1, 0, 0 }, { 0, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0, 0, 0, 0 }, { 0,-1, 0,-1,-1,-1,-1, 0,-1,-1,-1, 0, 0,-1,-1,-1,-1,-1,-1, 0 }, { 0,-1, 0, 0, 0, 0, 0, 0,-1,-1,-1, 0, 0, 0, 0, 0, 0, 0,-1, 0 }, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,-1,-1,-1, 0,-1, 0 }, {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 0,-1, 0,-1, 0 }, {-1,-1,-1, 0,-1,-1,-1,-1,-1,-1, 0, 0,-1,-1,-1,-1,-1, 0,-1, 0 }, {-1,-1, 0, 0,-1,-1, 0, 0, 0, 0, 0, 0,-1, 0, 0, 0, 0, 0,-1, 0 }, { 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0 }, { 0,-1,-1,-1, 0, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0, 0, 0, 0, 0, 0 }, { 0,-1,-1,-1,-1,-1, 0,-1,-1,-1, 0,-1,-1, 0,-1,-1,-1,-1,-1,-1 }, { 0, 0, 0, 0, 0, 0, 0,-1,-1,-1, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1 }, }; //fonction principale int main () { int i,j; i=4, j=0; droite (i,j); gauche (i,j); Monter (i,j); Descendre (i,j); Affiche (T); } void affiche(int T[20][20]) { int i,j; printf("Labyrinthe "); for(i=0; i< 20;i++){ for(j=0; j< 20;j++){ if (T[i][j] == 0) { printf(" ",T[i][j]); } else { if (T[i][j] == -1) { printf("a",T[i][j]); } else { printf("%d",T[i][j]); } } } printf(" "); } printf(" "); } //fonction droite qui permet de parcourir le labyrinthe vers la droite void droite ( int i, int j) { for(j=0;j<20;j++) { if (T[i][j+1]== 0) { T[i][j+1]=T[i][j] + 1; } else { if (T[i][j+1]==-1) { for(i=4;i<20;i++) { if (T[i][j+1]== 0) { T[i+1][j]=T[i][j] + 1; } else return; } } else return; } } } //fonction gauche qui permet de parcourir le labyrinthe vers la gauche void gauche ( int i, int j) { for(j=0;j<20;j++) { if (T[i][j-1]== 0) { T[i][j-1]=T[i][j] + 1; } else return; } } //fonction monter qui permet de parcourir le labyrinthe vers le haut void monter ( int i, int j) { for(i=4;i>0;i--) { if (T[i-1][j]== 0) { T[i-1][j]=T[i][j] + 1; } else return; } } //fonction descendre qui permet de parcourir le labyrinthe vers la bas void bas( int i, int j) { for(i=4;i<20;i++) { if (T[i+1][j]== 0) { T[i+1][j]=T[i][j] + 1; } else return; } }

Ombitious_Developper · Answer

Salut:

Si tu veux par exemple laisser un robot explorer le labyrinthe jusqu'à trouver la sortie :
ajoute une variable pour gérer la direction du robot:

enum {
BAS,
HAUT,
GAUCHE,
DROITE};

puis essayer de faire un parcours circulaire.

yann_lo_san · Answer

La solution adoptée dans la littérature algorithmique est de créer une pile FIFO qui sauve le chemin emprunté par l'objet circulant dans le labyrinthe pour pouvoir se replier quant une impasse est trouvée.
Cela donne le moyen de chercher une sortie, mais pas le meilleur chemin !

Parcourir un labyrinthe

2 réponses

Votre réponse

Discussions similaires