Vérification de sortie de labyrinthe⚓︎
Un labyrinthe rectangulaire délimité et entouré par des buissons peut être schématisé par un tableau 2D : une liste de listes d'entiers égaux à 0 ou 1.
1désigne un buisson dans lequel on s'entrave.0désigne un emplacement libre, où l'on peut circuler vers toute autre case libre immédiatement au Nord, au Sud, à l'Est ou à l'Ouest.- Il y a au moins trois lignes et trois colonnes.
- La première et la dernière ligne sont remplies de
1. - La première et la dernière colonne sont remplies de
1.
- La première et la dernière ligne sont remplies de
- Le départ est sur la deuxième ligne, deuxième colonne. Cette case est libre.
- La sortie est sur l'avant-dernière ligne, avant-dernière colonne.
Un chemin est décrit par une chaine de caractères composée de lettres parmi "NSEO".
- Le Nord (
N), c'est vers le haut du tableau ; \(-1\) pour la ligne, même colonne. - Le Sud (
S), c'est vers le bas du tableau ; \(+1\) pour la ligne, même colonne. - L'Est (
E), c'est vers la droite du tableau ; même ligne, \(+1\) pour la colonne. - L'Ouest (
O), c'est vers la gauche du tableau ; même ligne, \(-1\) pour la colonne.
Écrire une fonction telle que verifie(labyrinthe, chemin) détermine, en renvoyant un booléen, si la description chemin permet d'aller du départ à la sortie du labyrinthe sans passer deux fois sur la même case, ni passer par des buissons.
La fonction pourra modifier labyrinthe à loisir.
Exemples
labyrinthe = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
chemin_0 = "EEEEEO"
chemin_1 = "EEEEES"
chemin_2 = "SSSSSEENNNEEEEEEESSOOOOSSSEEEESS"
labyrinthe_0 = [ligne.copy() for ligne in labyrinthe]
labyrinthe_1 = [ligne.copy() for ligne in labyrinthe]
labyrinthe_2 = [ligne.copy() for ligne in labyrinthe]
assert not verifie(labyrinthe_0, chemin_0), "retour sur ses pas"
assert not verifie(labyrinthe_1, chemin_1), "entrée dans les buissons"
assert verifie(labyrinthe_2, chemin_2)
Code à compléter (constante DECALAGE et fonction verifie) :
DECALAGE = {'N': (-1, 0), 'S': ...}bksl-nlMARQUEpy-undLIBRE = 0bksl-nlMARQUEpy-undBUISSON = 1bksl-nlMARQUEpy-undVU = 2bksl-nlbksl-nldef verifie(labyrinthe, chemin):bksl-nl ipy-undentree, jpy-undentree = 1, 1bksl-nl ipy-undsortie, jpy-undsortie = ..., ...bksl-nlbksl-nl i, j = ipy-undentree, jpy-undentreebksl-nl for direction in chemin:bksl-nl labyrinthe[i][j] = MARQUEpy-undVUbksl-nl di, dj = DECALAGE[...]bksl-nl i, j = ..., ...bksl-nl if labyrinthe[i][j] != ...:bksl-nl return ...bksl-nl return (i, j) == ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nllabyrinthe = [bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],bksl-nl [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],bksl-nl [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],bksl-nl [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],bksl-nl [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]bksl-nl]bksl-nlbksl-nlcheminpy-und1 = "EEEEES"bksl-nlcheminpy-und2 = "SSSSSEENNNEEEEEEESSOOOOSSSEEEESS"bksl-nlbksl-nllabyrinthepy-und1 = [ligne.copy() for ligne in labyrinthe]bksl-nllabyrinthepy-und2 = [ligne.copy() for ligne in labyrinthe]bksl-nlbksl-nlassert not verifie(labyrinthepy-und1, cheminpy-und1)bksl-nlassert verifie(labyrinthepy-und2, cheminpy-und2)bksl-nlbksl-nlDECALAGE = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'O': (0, -1)}bksl-nlMARQUEpy-undLIBRE = 0bksl-nlMARQUEpy-undBUISSON = 1bksl-nlMARQUEpy-undVU = 2bksl-nlbksl-nldef verifie(labyrinthe, chemin):bksl-nl ipy-undentree, jpy-undentree = 1, 1bksl-nl ipy-undsortie, jpy-undsortie = len(labyrinthe) - 2, len(labyrinthe[0]) - 2bksl-nlbksl-nl i, j = ipy-undentree, jpy-undentreebksl-nl for direction in chemin:bksl-nl labyrinthe[i][j] = MARQUEpy-undVUbksl-nl di, dj = DECALAGE[direction]bksl-nl i, j = i + di, j + djbksl-nl if labyrinthe[i][j] != MARQUEpy-undLIBRE:bksl-nl return Falsebksl-nl return (i, j) == (ipy-undsortie, jpy-undsortie)bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nllabyrinthe = [bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],bksl-nl [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],bksl-nl [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],bksl-nl [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],bksl-nl [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],bksl-nl [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]bksl-nl]bksl-nlbksl-nlcheminpy-und1 = "EEEEES"bksl-nlcheminpy-und2 = "SSSSSEENNNEEEEEEESSOOOOSSSEEEESS"bksl-nlbksl-nllabyrinthepy-und1 = [ligne.copy() for ligne in labyrinthe]bksl-nllabyrinthepy-und2 = [ligne.copy() for ligne in labyrinthe]bksl-nlbksl-nlassert not verifie(labyrinthepy-und1, cheminpy-und1)bksl-nlassert verifie(labyrinthepy-und2, cheminpy-und2)bksl-nlbksl-nl
A
Z