Plus Court Chemin dans un Labyrinthe
BFS sur grille 2D
Enonce
Trouver le plus court chemin dans un labyrinthe (grille 2D). Retourner la longueur du chemin, ou -1 si impossible.
⚠ Bonus : Reconstruire et afficher le chemin.
Signature attendue
def plus_court_chemin(grille: list, depart: tuple, arrivee: tuple) -> int:Exemple
plus_court_chemin([[0, 0, 1], [1, 0, 0], [0, 0, 0]], (0, 0), (2, 2))→4
📖 Rappel de cours
Un labyrinthe peut être modélisé par une grille 2D où 0 = passage et 1 = mur. Le BFS sur grille donne le plus court chemin (en nombre de cases).
Modélisation :
Chaque case $(i,j)$ est un sommet. Les voisins sont les 4 cases adjacentes (haut, bas, gauche, droite) si elles sont dans la grille et ne sont pas des murs.
BFS :
Complexité : $O(n \times m)$ où $n \times m$ est la taille de la grille.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Algorithme de Prim
- Algorithme de Kruskal
- Coloration de Graphe
- Représentations d'un Graphe
- Test de Bipartisme
- Détection de Cycle (graphe orienté)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.