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).
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).
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.
cellule = Cellule(...)
Réponse
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 |
|
Réponse
🐍 Script Python | |
---|---|
4 5 6 7 8 |
|
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 |
|
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 |
|
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
.
Réponse
🐍 Script Python | |
---|---|
18 19 20 |
|
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.
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.
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 |
|
Réponse
🐍 Script Python | |
---|---|
22 23 24 25 26 27 |
|
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.