Exercice 5 - Questions 5 et 6 : Diviser pour régn… · Bac Numérique et Sciences Informatiques Métropole 2022 (sujet 2)

Cet exercice aborde la programmation objet et la méthode diviser pour régner.

Un labyrinthe est composé de cellules possédant chacune quatre murs (voir ci-dessus). 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}

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.

La méthode creer_labyrinthe permet, à partir d'une grille, de créer un labyrinthe de hauteur haut et de longueur long dont la cellule en haut à gauche est de coordonnées ( ligne, colonne).

Le cas de base correspond à 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 25 à 30 de la méthode creer_labyrinthe traitant le cas de base:

24

def creer_labyrinthe(self, ligne, colonne, haut, long):

25

if haut == 1: # Cas de base

26

for k in range(...):

27

self.creer_passage(ligne, k, ligne, k+1)

28

elif long == 1: # Cas de base

29

for k in range(...):

30

self.creer_passage(...)

31

else: # Appels récursifs

32

# Code non étudié (Ne pas compléter)

6.

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

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

Si haut >= long, on coupe horizontalement la grille en deux sous-labyrinthes de même dimension.

Si haut < long, 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.