TD 13 - Matrice et pile

1 Parcourir un labyrinthe

On décide de coder un labyrinthe avec une matrice \(M\) de taille \(n \times m\). On utilise le nombre 0 pour un espace libre et 1 pour un mur ; la sortie est codée par le nombre 3. On donne aussi le point d’entrée sous la forme de coordonnées \([l,c]\).

On utilise deux autres matrices : \(V\) pour vérifier si la case a été visitée et \(C\) pour retenir le chemin emprunté.

1.1 Exercice 1

Écrire un algorithme qui renvoie une pile contenant toutes les cases adjacentes disponibles (non visitées et libres) d’une case donnée en paramètre.

1.2 Exercice 2

Écrire un algorithme qui affiche le chemin de la case de départ à celle d’arrivée en utilisant la matrice \(C\) donnée en paramètre (cette matrice contient le prédécesseur de chaque case visitée). Vous utiliserez une pile.

1.3 Exercice 3

Écrire un algorithme qui affiche le chemin pour sortir d’un labyrinthe si c’est possible. Il prendra comme argument la matrice \(M\) et les coordonnées de la case de départ et utilisera les algorithmes des exercices précédents.

NoteRappel : DFS avec pile

L’algorithme utilise un parcours en profondeur (DFS) avec une pile : 1. Empiler la case de départ 2. Tant que la pile n’est pas vide : - Dépiler une case - Si c’est la sortie : succès - Sinon, empiler les voisins non visités 3. Si pile vide sans trouver la sortie : échec

2 En plus

2.1 Exercice 4 🏠

Modifier l’algorithme de parcours de labyrinthe pour qu’il affiche tous les chemins permettant de sortir dans le cas où le labyrinthe possède plusieurs sorties.

2.2 Exercice 5 : Parcours du labyrinthe par la main gauche 🏠

On souhaite explorer un labyrinthe en utilisant la stratégie dite de la “main gauche” : à chaque étape, on avance en gardant la main gauche au contact du mur, ce qui garantit de trouver une sortie si le labyrinthe est simplement connexe (sans îlots isolés).

  1. Appliquer la stratégie “main gauche” sur l’exemple suivant :

    \[\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 3 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}\]

    L’entrée se situe en \((2,2)\) et la sortie en \((2,5)\).

  2. La stratégie “main gauche” consiste à empiler, pour chaque étape, les cases à visiter dans l’ordre inverse des aiguilles d’une montre en commençant par la direction située à gauche par rapport au déplacement précédent.

    1. En connaissant les coordonnées de la case d’origine et celle d’arrivée, expliquez comment déterminer quelle est la direction suivie, puis en déduire les coordonnées de la case “à gauche” de la direction actuelle.

    2. On adopte un tableau DIR de quatre cases correspondant aux directions cardinales (Nord, Est, Sud, Ouest), chaque case définissant la modification d’indices nécessaire pour atteindre une case voisine. Par exemple, DIR[1] = \([-1,0]\) représente le mouvement vers le haut (Nord), car il faut retirer 1 à l’indice de ligne et rien à celui de la colonne.

    Écrire un algorithme qui, connaissant la direction courante et la position, renvoie une pile avec les coordonnées des cases voisines à explorer dans l’ordre : à gauche, devant, à droite.

  3. Écrire l’algorithme d’un parcours main gauche à partir d’une case d’entrée.

NotePrincipe de la règle de la main gauche

Ordre de priorité : 1. Tourner à gauche si possible 2. Sinon aller tout droit si possible 3. Sinon tourner à droite si possible 4. Sinon faire demi-tour

Tableau des directions :

DIR[0] = [-1, 0]  # Nord (↑)
DIR[1] = [0, 1]   # Est  (→)
DIR[2] = [1, 0]   # Sud  (↓)
DIR[3] = [0, -1]  # Ouest (←)

Pour tourner à gauche : (direction - 1) mod 4