Aller au contenu

Labyrinthe en POO⚓︎

D'après 2022, Métropole, J2, Ex. 5

Un labyrinthe est composé de cellules possédant chacune quatre murs (voir ci-dessous). La cellule en haut à gauche du labyrinthe est de coordonnées (0, 0).

Le labyrinthe

On définit la classe Cellule ci-dessous. Le constructeur possède un attribut murs de type dict dont les clés sont 'N', 'E', 'S' et 'O' et dont les valeurs sont des booléens (True si le mur est présent et False sinon).

🐍 Script Python
class Cellule:
    def __init__(self, murNord, murEst, murSud, murOuest):
        self.murs = {
            "N": murNord,
            "E": murEst,
            "S": murSud,
            "O": murOuest
            }

1. Recopier et compléter sur la copie l'instruction Python suivante permettant de créer une instance cellule de la classe Cellule possédant tous ses murs sauf le mur Est.

🐍 Script Python
cellule = Cellule(...)
Réponse
🐍 Script Python
cellule = Cellule(True, False, True, True)

2. Le constructeur de la classe Labyrinthe ci-dessous possède un seul attribut grille.

Cette grille est un tableau à deux dimensions hauteur et largeur contenant des cellules possédant chacune ses quatre murs.

Recopier et compléter sur la copie les lignes 4 à 8 de la classe Labyrinthe.

🐍 Script Python
1
2
3
4
5
6
7
8
9
class Labyrinthe:
    def __init__(self, hauteur, largeur):
        self.grille = []
        for i in range(...):
            ligne = []
            for j in range(...):
                cellule = ...
                ligne.append(...)
            self.grille.append(ligne)
Réponse
🐍 Script Python
4
5
6
7
8
for i in range(hauteur):
    ligne = []
    for j in range(largeur):
        cellule = Cellule(True, True, True, True)
        ligne.append(cellule)

Pour générer un labyrinthe, on munit la classe Labyrinthe d'une méthode creer_passage permettant de supprimer des murs entre deux cellules ayant un côté commun afin de créer un passage.

Cette méthode prend en paramètres les coordonnées i1, j1 d'une cellule notée cellule1 et les coordonnées i2, j2 d'une cellule notée cellule2 et crée un passage entre cellule1 et cellule2.

🐍 Script Python
10
11
12
13
14
15
16
17
18
19
20
def creer_passage(self, i1, j1, i2, j2):
        cellule1 = self.grille[i1][j1]
        cellule2 = self.grille[i2][j2]
        # cellule2 au Nord de cellule1
        if i1 - i2 == 1 and j1 == j2:
            cellule1.murs["N"] = False
            ...
            # cellule2 à l'Ouest de cellule1
        elif ...:
            ...
            ...

3. La ligne 15 permet de supprimer le mur Nord de cellule1. Un mur de cellule2 doit aussi être supprimé pour libérer un passage entre cellule1 et cellule2.

Écrire l'instruction Python que l'on doit ajouter à la ligne 16.

Réponse
🐍 Script Python
16
cellule2.murs['S'] = False

4. Recopier et compléter sur la copie le code Python des lignes 18 à 20 qui permettent le traitement du cas où cellule2 est à l'Ouest de cellule1.

Deux cellules

Réponse
🐍 Script Python
18
19
20
elif j1 - j2 == 1 and i1 == i2:
    cellule1.murs["O"] = False
    cellule2.murs["E"] = False

Pour créer un labyrinthe, on utilise la méthode diviser pour régner en appliquant récursivement l'algorithme creer_labyrinthe sur des sous-grilles obtenues en coupant la grille en deux puis en reliant les deux sous-labyrinthes en créant un passage entre eux.

Création récursive

Les cas de base correspondent à la situation où la grille est de hauteur 1 ou de largeur 1. Il suffit alors de supprimer tous les murs intérieurs de la grille.

Cas de base

5. Recopier et compléter sur la copie les lignes 22 à 27 de la méthode creer_labyrinthe traitant le cas de base.

🐍 Script Python
21
22
23
24
25
26
27
28
29
def creer_labyrinthe(self, i, j, hauteur, largeur):
        if hauteur == 1:  # Cas de base
            for k in range(...):
                self.creer_passage(i, j + k, i, j + k + 1)
        elif largeur == 1:  # Cas de base
            for k in range(...):
                self.creer_passage(...)
        else:   # Appels récursifs
                # Code non étudié (Ne pas compléter)
Réponse
🐍 Script Python
22
23
24
25
26
27
if hauteur == 1:  # Cas de base
    for k in range(largeur - 1):
        self.creer_passage(i, j + k, i, j + k + 1)
elif largeur == 1:  # Cas de base
    for k in range(hauteur - 1):
        self.creer_passage(i + k, j, i + k + 1, j)

6. Dans cette question, on considère une grille de hauteur hauteur = 4 et de longueur largeur = 8 dont chaque cellule possède tous ses murs.

On fixe les deux contraintes supplémentaires suivantes sur la méthode creer_labyrinthe :

  • Si hauteur est supérieure ou égale à largeur, on coupe horizontalement la grille en deux sous-labyrinthes de même dimension ;
  • Si hauteur est strictement inférieure à largeur, on coupe verticalement la grille en deux sous-labyrinthes de même dimension.

L'ouverture du passage entre les deux sous-labyrinthes se fait le plus au Nord pour une coupe verticale et le plus à l'Ouest pour une coupe horizontale.

Dessiner le labyrinthe obtenu suite à l'exécution complète de l'algorithme creer_labyrinthe sur cette grille.

Réponse

Labyrinthe final