Problème — Sortir d'un labyrinthe

Problème — Sortir d'un labyrinthe.

Un labyrinthe est donné par une liste de chaînes de même longueur : # désigne un mur, . une case libre, S le départ et E la sortie. On se déplace d'une case à une case voisine libre (haut, bas, gauche, droite).

grille = ["S.#.....",
          ".##.###.",
          "....#...",
          "#.#...#E"]

• Expliquer comment voir ce labyrinthe comme un graphe. Faut-il construire ses listes d'adjacence à l'avance ?
• Écrire une fonction plus_court(grille) qui renvoie le nombre minimal de déplacements pour aller de S à E, ou $-1$ si la sortie est inaccessible.
• Appliquer à la grille ci-dessus, puis à la même grille où la case libre à gauche de E (ligne $3$, colonne $5$, en numérotant à partir de $0$) serait un mur.