Chemin le plus court sur une grille
Étant donné un labyrinthe représenté sous la forme d’une grille de
r lignes et c colonnes, on vous demande de déterminer la longueur du chemin le plus court entre la cellule de départ et la cellule d’arrivée.Le labyrinthe est représenté de la façon suivante :
- Le sol est un point (
.).
- Les murs sont des dièses (
#).
- Le point de départ est la lettre majuscule
S.
- La cellule d’arrivée est la lettre majuscule
E.
Vous pouvez vous déplacer entre deux cases adjacentes (gauche, droite, haut ou bas) si celles-ci ne constituent pas un mur.
On vous demande de trouver la longueur du plus court chemin entre la cellule de départ et celle d’arrivée.
Entrée
La première ligne de l’entrée contient deux entiers
r et c (1 ≤ r, c ≤ 1000).Les
r lignes suivantes comportent c colonnes de caractères permettant de décrire la grille. Chaque cellule peut être un sol (.), un mur (#), un point de départ (S), ou un point d’arrivée (E). Il est garanti qu’il n’y a qu’un seul S et un seul E dans toute la grille.Sortie
Le programme doit afficher la longueur du chemin le plus court entre
S et E. S’il n’existe aucun chemin entre S et E, le programme doit imprimer Impossible.Exemples
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Conseil
Il n’est pas toujours nécessaire de construire un graphe explicite pour exécuter un algorithme de recherche en largeur (BFS). Parfois, il est possible d’exploiter des graphes implicites, comme ici où la grille joue le rôle de graphe.
Indice
Vous pouvez traiter la grille comme votre graphe et utiliser un tableau à deux dimensions
d[][] pour représenter la distance la plus courte entre la cellule de départ et chaque cellule visitée.Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB