Sortir du labyrinthe

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 13 — Parcours de graphes

Énoncé

Résoudre un labyrinthe donné sous forme de grille de caractères (# pour mur, . pour passage libre) en trouvant le plus court chemin de l'entrée $E$ à la sortie $S$ .

Corrigé

On implémente un BFS sur le graphe implicite de la grille :

from collections import deque

def resoudre_labyrinthe(plan: list, E: tuple, S: tuple):
    p, q = len(plan), len(plan[0])
    dist, pere = {E: 0}, {}
    file = deque([E])
    while file:
        (i, j) = file.popleft()
        if (i, j) == S:
            break
        for (ni, nj) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= ni < p and 0 <= nj < q and plan[ni][nj] == "." and (ni, nj) not in dist:
                dist[(ni, nj)] = dist[(i, j)] + 1
                pere[(ni, nj)] = (i, j)
                file.append((ni, nj))
    if S not in dist:
        return (None, None)
    # Reconstruction du chemin via l'arbre des pères
    c = [S]
    while c[-1] != E:
        c.append(pere[c[-1]])
    c.reverse()
    return (dist[S], c)

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.