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.

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

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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013s3_8ufvIy n7GaS1me(P24C:Vjtwi]D[hE)6OobcdUgM/0lABp!QrLF-,}=+Nk95R{050P0s0B0o0D0V0b0k0O0V0o0b0b0+010B0D0Y010406050b0f0r0r0o0#0j040p0M0V0f160M0l050T1d1f1h1j1b0Y041s1z051C0T1C1E1z1b0P0D0h0~1012140H0D0R0H0V1S0H0B19050_0N0V0s1N1113011R1T1V1T0B1#1%1Z0B0N0M0P1j1!0#1A0B0H0~1m0b0Y0o0l140v011)1P010g0{0s0l0o0r0s1Z24262b1+2e1%2h2j190a0k0u0#0M0Y0M0b0D1p0l0k0@220#0#0s0O2E1s2m0l1A0T202R0B1~1}1 0P2o141V0l2g2B1Z1K1M0 1*2#0D2%0l1`1L1Z0Y2K1A2P2R2|1c252F2-2c2=0#1g0V190k0q2O301a2 2n321+3436380v3b263d2P2!013i0o37040k0c3m2Q1b3p3g143s3u0k0w3y3o303q3E380:3I3A3K3C3r0M353t380K3P3e311O3h3U3j3v0m3Z3B3$3D3(3W3v0e3,3R3.3T3V3F0/3@3f3_3M040q0U3~3#2.3`3)0q3a1t3c3Q3 47410q3l4c3n4e46333:3u0q3x4k3z3!3L4p190q3H4t3J4f4o3{4y3O4B4m4w4F423Y4I4v3S4h3+4O3-4g4x423?4B1B2`1s2+2U0P2Y3q0O1`2k1A4%1D4#2~4Z4,0@2{3^4g190F0I0x0W0$0W0n0I3I0k4P3_0M190+56584718040=3I5e2c0b2904010-015j4U2c5g0y5d5t1+5g0t5s4{2c5a040(5C4D1+0r0D4y5I4n5z190)5x5D5K5M04444Z5y145g0J5S4B575!015m19010p5r5Z5U5#195w5)5k5Q045B5=5J145L5N5 5P5@045(2|5*5?01625X5O3q5$683c6a605,5n010I5;2~5+5v5T6l5A6f3S6d5Y6r6b5g6i3n6k656c5W4b6B6v195%6u6H5-5o0L6q3c5{665_696W016w643q6z6x3_6D6P3q5F5H6%6y6J6*5f6N0*453L190S0W0;0!0Q0I0d0$0i0X0;555`5+5F5c7a6b6)4T6b0l6}6 71730X0Q0i0p0p0L0-6-3S7c7v3_6d6K4d6!7j046~70720d0z0Q7y477x7e6l6d4j2|067U6!0.190@0g6@2c0C387#3h0g190h0s0#0D2e0s7)665~6L6H7E100N0j7/0l207=6;6+5R7M33190O0H0s5L1r836^040J6Y4d0k8k6G6|040D0d2g2V0s827_6g857P7`190A8q802K8u6j6!7O6Z5+7A7?6#8x8J7f6?4I8l8m4Q198p0b3U168F3n6!6,8y8n8B8Y0#8!861+8I8G5+0l0N192r8M6$8v8V047|7~2:818{6N8/146/966I197S6V6s8O8=7i8^8 2g945}8M7{0o7}7 938e5u190G8M7g8}84040E0J99988)6=9b3P068T7D8W9l6E2Q8U408A9E5b997E8p8r8E9O9W8A8C8s8#3z9L5+7X040g3U9$041K2K2M0D1q9E7%8o8d8P6l7E898b2:9l8i4l8T9,7i8_9p91808a9l9w9t3h9Naj660Eai9z4|040A9l0E9U047da08z7F7l7I7K3Pa98l9M9?0D9#9G9S9?ataM7N9VaQ87044~505254ah9n7Y0D9^2Nam8N9BaFaG9RaraKa*8(az8*away9ga1ala@7w190,9=1KaLa~aNaPb5aR04b1aTakaOa-aG7W8W7!bc3Dac9q92aga=9va#8oauap9dabasauaw0Za`6FaI7G7m747678a6bfa.8kbh042K0B0f0#9 a{6H0.0O190%3t0b9*1aaa6l9.bQbSbUbD9e9ma*9Xb4bVa^bq8ga_bC9Q8%197^bwa|8o0d8,8.b`9P3vaI8+8Z0Db%b b{4O0T4^0s2R2_cl4$1L4(2U2W2S1_1{2U9p1%2R4%1b0T0@0_0{0b04.