Plus court chemin dans un labyrinthe ASCII (BFS)

Trouver le plus court chemin entre un point de départ S et une sortie E dans un labyrinthe représenté par une grille ASCII, en utilisant une recherche en largeur (BFS).

75 minPublié le 20 mai 2026Proposé par Anonyme

Défi

// Lisez attentivement, codez sur votre machine

Énoncé

Le programme lit une grille ASCII représentant un labyrinthe : # est un mur, . est un couloir libre, S est la case de départ, E est la sortie. Les déplacements autorisés sont haut, bas, gauche, droite (pas de diagonale). Le programme affiche la longueur du plus court chemin (en nombre de cases, départ et arrivée inclus). Si aucun chemin n'existe, il affiche -1.

Contraintes

La grille fait au plus 100 × 100 cases.
Il y a exactement un S et un E dans la grille.
Les bords de la grille sont toujours des murs.
Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard (file/queue pour le BFS).

Exemple

Entrée :
#######
#S....#
#.###.#
#.#E..#
#.....#
#######

Sortie :
7

Chemin : S(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)→(3,3)=E, soit 7 cases.

Entrée :
#####
#S###
###E#
#####

Sortie :
-1

Espace solution

Proposer une solution

Connectez-vous ou créez un compte pour envoyer votre code (aucune exécution côté serveur — on stocke juste le texte pour la communauté).

Se connecter Créer un compte

Défi précédentParser un CSV avec guillemets et virgules échappées Défi suivant Trouver le plus court mot d'une phrase

// À garder en tête

D'abord, faire marcher
On ne cherche pas à optimiser : d'abord, on fait marcher le truc. Optimiser vient ensuite — et ça aussi, ça s'apprend. (Si un défi porte sur l'optimisation, son énoncé le précise.)
Pas de mauvaise réponse
Il n'y a pas de mauvaise réponse à un défi. Le but, c'est de le faire. Ce qui compte, c'est de s'entraîner.
Trop dur ? Au suivant
Un défi te résiste ? N'hésite pas à en prendre un autre. Ils seront encore là demain.