Aller au contenu

Vérification de sortie de labyrinthe⚓︎

Labyrinthe de buisson

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.

  • 1 désigne un buisson dans lequel on s'entrave.
  • 0 dé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.
  • 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.

Code à compléter (constante DECALAGE et fonction verifie) :

🐍 Script Python
DECALAGE = {'N': (-1, 0), 'S': ...}
MARQUE_LIBRE = 0
MARQUE_BUISSON = 1
MARQUE_VU = 2

def verifie(labyrinthe, chemin):
    i_entree, j_entree = 1, 1
    i_sortie, j_sortie = ..., ...

    i, j = i_entree, j_entree
    for direction in chemin:
        labyrinthe[i][j] = MARQUE_VU
        di, dj = DECALAGE[...]
        i, j = ..., ...
        if labyrinthe[i][j] != ...:
            return ...
    return (i, j) == ...

Exemples

🐍 Script Python
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)

labyrinthe

###
# 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-und0 = "EEEEEO"bksl-nlcheminpy-und1 = "EEEEES"bksl-nlcheminpy-und2 = "SSSSSEENNNEEEEEEESSOOOOSSSEEEESS"bksl-nlbksl-nllabyrinthepy-und0 = [ligne.copy() for ligne in labyrinthe]bksl-nllabyrinthepy-und1 = [ligne.copy() for ligne in labyrinthe]bksl-nllabyrinthepy-und2 = [ligne.copy() for ligne in labyrinthe]bksl-nlbksl-nlassert not verifie(labyrinthepy-und0, cheminpy-und0), "retour sur ses pas"bksl-nlassert not verifie(labyrinthepy-und1, cheminpy-und1), "entrée dans les buissons"bksl-nlassert verifie(labyrinthepy-und2, cheminpy-und2)bksl-nlbksl-nl# autres testsbksl-nlimport copybksl-nlbksl-nl# test minimalistebksl-nlbksl-nllab2 = [bksl-nl [1, 1, 1],bksl-nl [1, 0, 1],bksl-nl [1, 1, 1],bksl-nl]bksl-nlbksl-nllab = copy.deepcopy(lab2)bksl-nlassert verifie(lab, "")bksl-nlbksl-nllab = copy.deepcopy(lab2)bksl-nlassert not verifie(lab, "N")bksl-nlbksl-nllab = copy.deepcopy(lab2)bksl-nlassert not verifie(lab, "S")bksl-nlbksl-nllab = copy.deepcopy(lab2)bksl-nlassert not verifie(lab, "E")bksl-nlbksl-nllab = copy.deepcopy(lab2)bksl-nlassert not verifie(lab, "O")bksl-nlbksl-nlbksl-nl# test 4×3bksl-nlbksl-nllab3 = [bksl-nl [1, 1, 1],bksl-nl [1, 0, 1],bksl-nl [1, 0, 1],bksl-nl [1, 1, 1],bksl-nl]bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert verifie(lab, "S")bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "SNS")bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "N")bksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "E")bksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "O")bksl-nlbksl-nlbksl-nl# test 3×4bksl-nlbksl-nllab3 = [bksl-nl [1, 1, 1, 1],bksl-nl [1, 0, 0, 1],bksl-nl [1, 1, 1, 1],bksl-nl]bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert verifie(lab, "E")bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "EOE")bksl-nlbksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "N")bksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "S")bksl-nllab = copy.deepcopy(lab3)bksl-nlassert not verifie(lab, "O")bksl-nlbksl-nlbksl-nl 5/5

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-nlNone

A

Z

Retour en haut de la page