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.

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)

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

Évaluations restantes : 10/10

.128013:LpM(40ed3N 1Ej}Vo5_An)Bh]6,cG[y!CFuvi2+DmsU7=wlSIatf-9O{RQrgPkb8/050j0i0!0Z0M0W0R0m0D0W0Z0R0R0U010!0M0d010406050R0K0Q0Q0Z0,0G040X0s0W0K160s0w050=1d1f1h1j1b0d041s1z051C0=1C1E1z1b0j0M0L0~1012140z0M0-0z0W1S0z0!19050_0:0W0i1N1113011R1T1V1T0!1#1%1Z0!0:0s0j1j1!0,1A0!0z0~1m0R0d0Z0w140N011)1P010#0{0i0w0Z0Q0i1Z24262b1+2e1%2h2j190a0m0.0,0s0d0s0R0M1p0w0m0@220,0,0i0D2E1s2m0w1A0=202R0!1~1}1 0j2o141V0w2g2B1Z1K1M0 1*2#0M2%0w1`1L1Z0d2K1A2P2R2|1c252F2-2c2=0,1g0W190m0n2O301a2 2n321+3436380N3b263d2P2!013i0Z37040m0k3m2Q1b3p3g143s3u0m0g3y3o303q3E380t3I3A3K3C3r0s353t380B3P3e311O3h3U3j3v0T3Z3B3$3D3(3W3v0;3,3R3.3T3V3F0%3@3f3_3M040n0h3~3#2.3`3)0n3a1t3c3Q3 47410n3l4c3n4e46333:3u0n3x4k3z3!3L4p190n3H4t3J4f4o3{4y3O4B4m4w4F423Y4I4v3S4h3+4O3-4g4x423?4B1B2`1s2+2U0j2Y3q0D1`2k1A4%1D4#2~4Z4,0@2{3^4g190P0o0I0v0c0v0E0o3I0m4P3_0s190U56584718040)3I5e2c0R2904010l015j4U2c5g0b5d5t1+5g0f5s4{2c5a040$5C4D1+0Q0M4y5I4n5z190C5x5D5K5M04444Z5y145g0x5S4B575!015m19010X5r5Z5U5#195w5)5k5Q045B5=5J145L5N5 5P5@045(2|5*5?01625X5O3q5$683c6a605,5n010o5;2~5+5v5T6l5A6f3S6d5Y6r6b5g6i3n6k656c5W4b6B6v195%6u6H5-5o0(6q3c5{665_696W016w643q6z6x3_6D6P3q5F5H6%6y6J6*5f6N0q453L190e0v0*0+0S0o0u0c0Y0y0*555`5+5F5c7a6b6)4T6b0w6}6 71730y0S0Y0X0X0(0l6-3S7c7v3_6d6K4d6!7j046~70720u0r0S7y477x7e6l6d4j2|067U6!0/190@0#6@2c0V387#3h0#190L0i0,0M2e0i7)665~6L6H7E100:0G7/0w207=6;6+5R7M33190D0z0i5L1r836^040x6Y4d0m8k6G6|040M0u2g2V0i827_6g857P7`190p8q802K8u6j6!7O6Z5+7A7?6#8x8J7f6?4I8l8m4Q198p0R3U168F3n6!6,8y8n8B8Y0,8!861+8I8G5+0w0:192r8M6$8v8V047|7~2:818{6N8/146/966I197S6V6s8O8=7i8^8 2g945}8M7{0Z7}7 938e5u190F8M7g8}84040A0x99988)6=9b3P068T7D8W9l6E2Q8U408A9E5b997E8p8r8E9O9W8A8C8s8#3z9L5+7X040#3U9$041K2K2M0M1q9E7%8o8d8P6l7E898b2:9l8i4l8T9,7i8_9p91808a9l9w9t3h9Naj660Aai9z4|040p9l0A9U047da08z7F7l7I7K3Pa98l9M9?0M9#9G9S9?ataM7N9VaQ87044~505254ah9n7Y0M9^2Nam8N9BaFaG9RaraKa*8(az8*away9ga1ala@7w190O9=1KaLa~aNaPb5aR04b1aTakaOa-aG7W8W7!bc3Dac9q92aga=9va#8oauap9dabasauaw0Ha`6FaI7G7m747678a6bfa.8kbh042K0!0K0,9 a{6H0/0D190J3t0R9*1aaa6l9.bQbSbUbD9e9ma*9Xb4bVa^bq8ga_bC9Q8%197^bwa|8o0u8,8.b`9P3vaI8+8Z0Mb%b b{4O0=4^0i2R2_cl4$1L4(2U2W2S1_1{2U9p1%2R4%1b0=0@0_0{0R04.