TP 2 — Le labyrinthe

Sortir d'un labyrinthe en explorant ses cases : parcours en profondeur avec une pile, puis en largeur avec une file — corrigés testés, pièges et observations.

Ce TP est le passage à la pratique du chapitre 2 : on explore un labyrinthe en suivant un algorithme, d'abord avec une pile (parcours en profondeur), puis avec une file (parcours en largeur). Le fichier Labyrinthe.java est fourni : il contient le labyrinthe, les méthodes pour le tester et un affichage graphique. Notre travail : écrire la classe Cellule et la classe Parcours dans le même paquetage tp2, en marquant les cases au fur et à mesure.

Six questions : la cellule (Q1), le parcours avec pile (Q2), la sortie bouchée (Q3), le parcours avec file (Q4), puis les versions « maison » avec la Pile et la File du TD 2 (Q5, Q6).

Le labyrinthe fourni

Le labyrinthe est un tableau de caractères de 41 × 41 : un # est un mur, un espace est un passage. L'entrée est en haut à gauche, aux coordonnées (0, 1) — x = colonne, y = ligne — et la sortie en bas à droite, à la dernière colonne et l'avant-dernière ligne. La classe fournie sait tout faire sauf se parcourir : elle expose de quoi tester un mur, une sortie, poser une marque (rose pour une case explorée, rouge pour le chemin final) et rafraîchir la fenêtre.

Un mini-labyrinthe : on entre en haut à gauche, on sort à droite. Les cases explorées restent marquées ; le chemin final est la pile au moment où la sortie est atteinte. Le cul-de-sac (pastille grise) a été dépilé en cours de route.

Méthode	Rôle
`Labyrinthe()`	crée le labyrinthe — ouvre une fenêtre
`int n()`	taille du labyrinthe (41 ici : autant de lignes que de colonnes)
`int[] entree()` / `int[] sortie()`	coordonnées de l'entrée / de la sortie
`boolean estMur(int x, int y)`	le tableau `murs[y].charAt(x) == '#'`
`boolean estSortie(int x, int y)`	teste si `(x, y)` est la case de sortie
`boolean estMarque(int x, int y)`	une marque (rose ou rouge) est-elle posée ?
`void poserMarque(int x, int y)`	pose une marque rose
`void poserMarqueChemin(int x, int y)`	pose une marque rouge (chemin final)

Chaque méthode existe aussi en version int[] (cellule sous forme de tableau {x, y}). Réflexe : passez entree() et sortie() en paramètre plutôt que de coder (0, 1) et (40, 39) en dur — si l'enseignant·e change de labyrinthe, votre code marche encore.

Pour tester sans fenêtre : le corrigé de cette page a été exécuté avec une version console du fichier (mêmes méthodes, même labyrinthe, pas d'affichage). Le code de Cellule et Parcours est rigoureusement identique — c'est l'intérêt d'écrire contre des méthodes plutôt que contre une fenêtre.

Q1 — la classe Cellule

Le parcours manipule des couples (x, y) : on commence donc par une petite classe Cellule, avec les deux attributs et un constructeur, plus un toArray() qui rend service pour les méthodes en version int[] de Labyrinthe.

Cellule.java

package tp2;

import java.util.Objects;

/**
 * Une cellule du labyrinthe : un couple (x, y).
 * x = numéro de colonne (gauche -> droite, à partir de 0)
 * y = numéro de ligne  (haut -> bas, à partir de 0)
 */
public class Cellule {

    public int x;
    public int y;

    public Cellule(int x, int y) {
        this.x = x;
        this.y = y;
    }

    /** Le tableau des deux coordonnées, pour les méthodes de Labyrinthe. */
    public int[] toArray() {
        return new int[] { x, y };
    }

    // equals/hashCode : nécessaires pour utiliser des Cellule comme clés
    // d'une Map (version « file » du parcours, question 4).

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Cellule)) {
            return false;
        }
        Cellule autre = (Cellule) o;
        return x == autre.x && y == autre.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

Pourquoi equals/hashCode dès maintenant ? Deux Cellule de mêmes coordonnées sont forcément des objets distincts (new Cellule(3, 4) != new Cellule(3, 4)). Sans equals/hashCode, Java les considérerait comme clés différentes dans une HashMap — ce dont on a besoin en Q4 pour retrouver « d'où je viens ».

Q2 — le parcours avec une pile

L'algorithme demandé, en français :

Empiler la cellule d'entrée et la marquer.
Tant que la pile n'est pas vide :
- soit c la cellule au sommet de la pile ;
- si c est la sortie → afficher « Sortie trouvée » et s'arrêter ;
- sinon, s'il existe une voisine de c qui n'est ni un mur ni une case marquée : la marquer et l'empiler (une seule par itération, même si plusieurs sont libres) ;
- sinon, dépiler : c'est un cul-de-sac.
Si la pile se vide avant d'avoir trouvé la sortie : aucun chemin n'existe.

La boucle du parcours, répétée tant que la pile n'est pas vide. Si la pile se vide avant la sortie : il n'y a pas de chemin.

À la fin, la pile contient une chaîne de cellules voisines de l'entrée jusqu'à la sortie : c'est le chemin, qu'on marque en rouge. Petit détail qui change tout : on marque une case au moment où on l'empile (pas au moment où on la dépile) — c'est ce qui empêche de revenir cent fois sur la même case.

Parcours.java

package tp2;

import java.util.Stack;

/**
 * Parcours du labyrinthe avec une pile (classe java.util.Stack) :
 * on suit un chemin, on empile les cases visitées, et on dépile
 * quand on est dans un cul-de-sac.
 */
public class Parcours {

    /**
     * Explore le labyrinthe à partir de l'entrée et renvoie true si la sortie
     * est atteinte. Les cases explorées sont marquées en rose, et le chemin
     * trouvé (contenu dans la pile à la fin) est marqué en rouge.
     */
    public static boolean explorer(Labyrinthe l) {
        Stack<Cellule> p = new Stack<>();

        Cellule depart = new Cellule(l.entree()[0], l.entree()[1]);
        p.push(depart);
        l.poserMarque(depart.x, depart.y); // éviter de ressortir par l'entrée

        boolean trouve = false;
        while (!p.isEmpty()) {
            Cellule c = p.peek();
            if (l.estSortie(c.x, c.y)) {
                trouve = true;
                break;
            }
            Cellule v = voisinExplorable(l, c);
            if (v != null) {
                // une seule nouvelle case par itération !
                l.poserMarque(v.x, v.y);
                p.push(v);
            } else {
                // tous les voisins sont des murs ou déjà marqués : cul-de-sac
                p.pop();
            }
            ralentir();
        }

        if (trouve) {
            for (Cellule c : p) {
                l.poserMarqueChemin(c.x, c.y);
            }
        } else {
            System.out.println("Il n'y a pas de chemin reliant l'entrée à la sortie");
        }
        return trouve;
    }

    /** La première voisine de c qui est explorable, ou null si aucune. */
    private static Cellule voisinExplorable(Labyrinthe l, Cellule c) {
        Cellule[] candidates = {
                new Cellule(c.x + 1, c.y), // droite
                new Cellule(c.x, c.y + 1), // bas
                new Cellule(c.x - 1, c.y), // gauche
                new Cellule(c.x, c.y - 1), // haut
        };
        for (Cellule v : candidates) {
            if (explorable(l, v.x, v.y)) {
                return v;
            }
        }
        return null;
    }

    /**
     * Une case est explorable si elle est dans la grille, sans mur,
     * et pas déjà marquée. Le test des bornes est indispensable : la case
     * d'entrée est sur le bord, et « estMur(-1, y) » planterait.
     */
    public static boolean explorable(Labyrinthe l, int x, int y) {
        if (x < 0 || y < 0 || x >= l.n() || y >= l.n()) {
            return false;
        }
        return !l.estMur(x, y) && !l.estMarque(x, y);
    }

    /** Ralentit la boucle pour que le remplissage rose soit visible. */
    private static void ralentir() {
        try {
            Thread.sleep(10);
        } catch (InterruptedException e) {
            // rien : le programme s'arrête de toute façon
        }
    }

    public static void main(String[] args) {
        Labyrinthe l = new Labyrinthe();
        if (explorer(l)) {
            System.out.println("Sortie trouvée");
        }
    }
}

Le piège des bords — à connaître par cœur

La case d'entrée est sur le bord : (0, 1). Sa voisine de gauche a pour coordonnées (-1, 1), et en testant naïvement l.estMur(-1, 1), le murs[y].charAt(x) de la classe fournie lève une StringIndexOutOfBoundsException — vérifié en test ! C'est pour ça que explorable teste les bornes en premier (x < 0 || y < 0 || x >= n || y >= n). Le bug ne se voit pas au début si l'ordre des voisines est favorable… mais il explose dès que la boucle revient sur l'entrée (par exemple en Q3, sortie bouchée).

Ce que vous devez voir à l'écran

La fenêtre se remplit de rose (les cases explorées) au fil du parcours, et dès la sortie atteinte, le chemin apparaît en rouge. Sur le labyrinthe fourni, avec l'ordre de test des voisines droite → bas → gauche → haut : 231 cases explorées et un chemin de 139 cases. Supprimez le ralentir() pour aller au bout instantanément.

Q3 — et si la sortie était bouchée ?

Le sujet demande de modifier le labyrinthe pour voir le comportement quand la sortie est inatteignable : on transforme la case de sortie en mur. C'est la dernière ligne du tableau murs (indice 39) qui contient la sortie — son dernier caractère doit passer de l'espace à #.

Labyrinthe.java — la ligne 39 avant / après

// avant :
"#     # #  # #             #      # # #  ",
// après (la sortie est murée) :
"#     # #  # #             #      # # # #",

Relancez : le rose se répand, se replie sur lui-même (les cul-de-sac se dépilent), puis la pile se vide et le programme affiche :

Il n'y a pas de chemin reliant l'entrée à la sortie

Toutes les cases atteignables depuis l'entrée sont alors marquées en rose : 836 cases sur le labyrinthe fourni. Et c'est ce scénario qui fait planter la version naïve du test des voisines quand la boucle revient jusqu'à l'entrée (voir le piège des bords plus haut) — avec le test des bornes, pas de problème.

Q4 — la même exploration avec une file

On remplace la pile par une file : on retire la tête (poll) et on ajoute toutes les voisines explorables en queue (offer). Le parcours progresse en largeur : d'abord la case d'entrée, puis ses voisines, puis les voisines de ses voisines… Le sujet propose de le faire dans Parcours ; on préfère créer ParcoursFile.java pour garder les deux versions (bon réflexe : un fichier = une responsabilité).

Comme la file ne suit pas un chemin unique, il faut retenir d'où chaque case a été découverte pour reconstruire le chemin : un HashMap<Cellule, Cellule> qui associe chaque case à son « père » — d'où le equals/hashCode de la Q1.

ParcoursFile.java

package tp2;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * Question 4 : le même parcours avec une file (Queue) au lieu d'une pile.
 * On retire la tête, on ajoute ses voisines non explorées en queue :
 * le parcours progresse « niveau par niveau » (en largeur).
 * Pour reconstruire le chemin, chaque case connaît son père (celle
 * depuis laquelle on l'a découverte) : on remonte de la sortie à l'entrée.
 */
public class ParcoursFile {

    public static boolean explorer(Labyrinthe l) {
        Queue<Cellule> file = new ArrayDeque<>();
        Map<Cellule, Cellule> pere = new HashMap<>(); // case -> d'où je viens

        Cellule depart = new Cellule(l.entree()[0], l.entree()[1]);
        file.offer(depart);
        l.poserMarque(depart.x, depart.y);
        pere.put(depart, null);

        Cellule arrivee = null;
        while (!file.isEmpty()) {
            Cellule c = file.poll();
            if (l.estSortie(c.x, c.y)) {
                arrivee = c;
                break;
            }
            // toutes les voisines explorables, pas une seule :
            // c'est ça, la différence avec la pile !
            Cellule[] candidates = {
                    new Cellule(c.x + 1, c.y),
                    new Cellule(c.x, c.y + 1),
                    new Cellule(c.x - 1, c.y),
                    new Cellule(c.x, c.y - 1),
            };
            for (Cellule v : candidates) {
                if (Parcours.explorable(l, v.x, v.y)) {
                    l.poserMarque(v.x, v.y);
                    pere.put(v, c);
                    file.offer(v);
                }
            }
            ralentir();
        }

        if (arrivee != null) {
            Cellule c = arrivee;
            while (c != null) {
                l.poserMarqueChemin(c.x, c.y);
                c = pere.get(c); // on remonte de père en père
            }
            return true;
        }
        System.out.println("Il n'y a pas de chemin reliant l'entrée à la sortie");
        return false;
    }

    public static void main(String[] args) {
        Labyrinthe l = new Labyrinthe();
        if (explorer(l)) {
            System.out.println("Sortie trouvée");
        }
    }
}

L'observation la plus intéressante du TP

Même labyrinthe, conteneur différent, comportements opposés (mesurés en test) :

	pile — Q2	file — Q4
Cases explorées	231	836 (toutes celles atteignables)
Chemin trouvé	139 cases	93 cases — le plus court

C'est logique : la file découvre les cases par distance croissante depuis l'entrée, donc la première fois qu'elle touche la sortie, c'est forcément par le plus court chemin. La pile, elle, plonge au bout de la première branche venue : elle trouve un chemin, pas le meilleur. (Le sujet demande seulement d'observer ce changement ; on est allés un cran plus loin en reconstruisant le chemin rouge via les pères.)

Q5 — avec la Pile du TD

Remplaçons java.util.Stack par notre classe Pile<E> du TD 2 (elle est dans le même paquetage, rien à importer). Le sujet demande que « le comportement reste exactement le même » : c'est le cas, car notre pile expose les mêmes noms de méthodes. Deux différences quand même :

// 1) la création (et supprimer l'import java.util.Stack)
Pile<Cellule> p = new Pile<>(l.n() * l.n()); // au lieu de : new Stack<>()

// 2) le marquage du chemin : java.util.Stack se parcourt au for-each,
//    notre Pile maison se draine simplement (l'ordre des marques n'importe pas)
while (!p.isEmpty()) {
    Cellule c = p.pop();
    l.poserMarqueChemin(c.x, c.y);
}

Pourquoi n() * n() comme capacité ? Une case n'est empilée qu'une fois au plus (on la marque au moment de l'empiler) : 41 × 41 = 1681 suffit toujours. En test : mêmes 231 cases explorées et même chemin de 139 cases qu'avec java.util.Stack — comportement identique, comme prévu.

Q6 — avec la File du TD

Même figure pour la question 4 : on remplace ArrayDeque par notre File<E> — les noms offer/poll/isEmpty sont les mêmes que ceux de Queue, et peek aussi existe chez nous.

// dans ParcoursFile.explorer (et supprimer l'import java.util.ArrayDeque)
File<Cellule> file = new File<>(l.n() * l.n()); // au lieu de : new ArrayDeque<>()

En test : mêmes 836 cases explorées, même chemin de 93 cases. Nos deux conteneurs du TD sont donc de vrais remplaçants d'usage général — c'était tout l'intérêt de les écrire nous-mêmes.

Ce qu'il faut savoir refaire

écrire une boucle d'exploration : regarder le sommet, tester la sortie, chercher une voisine explorable, l'empiler, sinon dépiler ;
marquer au moment d'empiler — jamais au dépilement ;
tester les bornes avant estMur/estMarque (explorable) ;
le chemin final est la pile elle-même (elle forme une chaîne de voisines) ;
pour la version file : ajouter toutes les voisines, et retenir les pères pour reconstruire le chemin — c'est le plus court.

Le fichier fourni

Labyrinthe.java

package tp2;

/*
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Written by C. Durr, Ecole Polytechnique, INF421
 *
 * Modifs I. Boneva, CRIStAL, Université de Lille
 *   and F. Guyomarch, L2EP, Université de Lille
 */

import java.awt.*;
import java.awt.event.*;

/**
 * Une classe simple pour afficher un labyrinthe stocké dans un tableau de
 * <code>String</code>.
 * 
 * @author <a href="mailto:frederic.guyomarch@univ-lille.fr">Frédéric
 *         Guyomarch</a> (ULille)
 * @version 1 sept. 2022
 */
class Labyrinthe extends Canvas {
    private static final long serialVersionUID = 1L;
    private String[] murs = {
            "#########################################",
            "    #        # # # #       #        # # #",
            "### # #### # # # # # ### ##### ## ### # #",
            "#   # #    # #   #   #   # #    #   #   #",
            "### ### ###### ######### # ###  # # ### #",
            "#          #   #     #   #        # #   #",
            "### ##### #### # ####### ### ###### ### #",
            "# # # # #  #     #   #       #    #     #",
            "# # # # # ## ### # # # # ###### ##### ###",
            "#   # #        #   #   #   #      #     #",
            "# #        # # # #   # # # # #      # # #",
            "# # # ###### # # ### # ### # # #### ### #",
            "# # #      # #     # #     # #  # #   # #",
            "# # ###### ##### ######### # #  # # ### #",
            "#   #      # #         #   #            #",
            "########## # ##### ######### ## ####### #",
            "#   #          #   # #     #      #     #",
            "### # ### #### ##### ### ######## ##### #",
            "#   #   #            #          # #     #",
            "### #####  ##### ########### #### ##### #",
            "#   #   #  #   #       #            # # #",
            "### # ### ## ### ####### # ######## # # #",
            "#     #    #           # #        # #   #",
            "### ### ######## ########### ## # # ### #",
            "#                # #         #  # # #   #",
            "### ### ###### # # # ########## ### ### #",
            "# # #      # # #   #       # #  #     # #",
            "# ##### # ## ##### # # # # # # ## ### ###",
            "#       #    # # # # # # #          #   #",
            "##### #### # # # # # ########## # ##" +
                    "" +
                    "#####",
            "#       #  #     #   #     #    # #     #",
            "# # #            # # #   #        # #   #",
            "# # # # ## ########### # # ### ###### ###",
            "# # # #    #   # # #   # # # #  #   #   #",
            "# ### #### # ### # ##### ### ## # # #  ##",
            "#   # #          # # #     #      #     #",
            "# ### ### ###### # # # # #####  # ### ###",
            "# #   #    #     #   # #        # #     #",
            "### ### # ## # ### ###########  ### # # #",
            "#     # #  # #             #      # # #  ",
            "#########################################" };
    private int[] sortie = new int[] { murs.length - 1, murs.length - 2 };
    private int[] entree = new int[] { 0, 1 };

    // coordonées (x,y) de l'entree
    int[] entree() {
        return entree;
    }

    // coordonées (x,y) de la sortie
    int[] sortie() {
        return sortie;
    }

    // est-ce la sortie ?
    boolean estSortie(int x, int y) {
        return x == sortie[0] && y == sortie[1];
    }

    // est-ce la sortie ?
    boolean estSortie(int[] s) {
        return s[0] == sortie[0] && s[1] == sortie[1];
    }

    // est-ce que (x,y) est un mur ?
    boolean estMur(int x, int y) {
        return murs[y].charAt(x) == '#';
    }

    // est-ce que (x,y) est un mur ?
    boolean estMur(int[] m) {
        return murs[m[1]].charAt(m[0]) == '#';
    }

    // la taille du labyrinthe, a la fois nb lignes et nb colonnes
    int n() {
        return murs.length;
    }

    static final char VIDE = 'a', ROUGE = 'b', ROSE = 'c';

    // les marques
    char[][] marque;

    // teste si la cellule (x,y) comporte une marque
    boolean estMarque(int x, int y) {
        return marque[x][y] != VIDE;
    }

    boolean estMarque(int[] c) {
        return marque[c[0]][c[1]] != VIDE;
    }

    // pose une marque
    void poserMarque(int x, int y) {
        marque[x][y] = ROSE;
        repaint();
    }

    void poserMarque(int[] c) {
        marque[c[0]][c[1]] = ROSE;
        repaint();
    }

    void poserMarqueChemin(int x, int y) {
        marque[x][y] = ROUGE;
        repaint();
    }

    void poserMarqueChemin(int[] c) {
        marque[c[0]][c[1]] = ROUGE;
        repaint();
    }

    static final int c = 8; // taille d'affichage d'une cellule

    // cree une fenetre et affiche le labyrinthe dedans
    Labyrinthe() {
        marque = new char[n()][n()];
        for (int i = 0; i < n(); i++) {
            for (int j = 0; j < n(); j++) {
                marque[i][j] = VIDE;
            }
        }

        Frame f = new Frame("Labyrinthe");
        f.setBounds(100, 100, c * n() + 20, c * n() + 60);
        f.add(this);

        f.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
        f.setVisible(true);
    }

    // ne pas effacer avant pour eviter que l'image clignote lors d'un
    // redessinement
    public void update(Graphics g) {
        paint(g);
    }

    public void paint(Graphics g) {
        // dessiner les murs et les marques
        for (int x = 0; x < n(); x++)
            for (int y = 0; y < n(); y++)
                if (estMur(x, y)) {
                    g.setColor(Color.gray);
                    g.fillRect(x * c, y * c, c, c);
                } else {
                    if (!estMarque(x, y))
                        g.setColor(Color.white);
                    else if (marque[x][y] == ROUGE)
                        g.setColor(Color.red);
                    else
                        g.setColor(Color.pink);
                    // g.setColor(estMarque(x,y) ? Color.red: Color.white);
                    g.fillOval(x * c + c / 4, y * c + c / 4, c - c / 2, c - c / 2);
                }
    }

    // ce main est juste la pour tester la classe
    public static void main(String args[]) {
        Labyrinthe l = new Labyrinthe();
        l.poserMarque(1, 1);
    }

}

tp2-labyrinthe.pdf

TP Piles et Files — Le labyrinthe · Structures de données · 3 pages

Consultation seule — téléchargement désactivé

Chargement du document…

TP 2 — Le labyrinthe

Les méthodes du fichier fourni (tout est en accès paquetage)

Corrigé — Cellule.java (avec equals et hashCode, utiles en Q4)

Corrigé — Parcours.java (parcours en profondeur)

Corrigé — ParcoursFile.java (parcours en largeur)

Labyrinthe.java — le fichier du TP, tel quel (à placer dans tp2)

Sur cette page