Percorso più breve su una griglia
Data una sorta di labirinto rappresentato come una griglia con
r righe e c colonne, l’obiettivo è trovare la lunghezza del percorso più breve dalla cella di partenza a quella di arrivo.La griglia è rappresentata nel modo seguente:
- Il pavimento è indicato con un punto (
.).
- I muri sono contrassegnati da un cancelletto (
#).
- Il punto di partenza è la lettera maiuscola
S.
- Il punto di arrivo è la lettera maiuscola
E.
È possibile muoversi verso le celle adiacenti (sinistra, destra, su, giù) se non sono ostacolate da muri.
Si richiede di calcolare la lunghezza del percorso più breve fra la cella di partenza e quella di arrivo.
Input
La prima riga dell’input contiene due interi
r e c (1 ≤ r, c ≤ 1000).Le successive
r righe contengono c colonne di caratteri che rappresentano la griglia. Ogni cella può essere un pavimento (.), un muro (#), un punto di partenza (S) o un punto di arrivo (E). Viene garantita l’esistenza di un solo S e un solo E in tutta la griglia.Output
Il programma deve stampare la lunghezza del percorso più breve da
S a E. Se non esiste alcun percorso da S a E, il programma deve stampare Impossible.Esempi
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Suggerimento
Non è sempre necessario costruire un grafo esplicito per eseguire un algoritmo di BFS. Spesso le griglie possono essere considerate come grafi impliciti e consentire comunque l’utilizzo di un BFS.
Consiglio
È possibile trattare la griglia come un grafo e utilizzare un array bidimensionale
d[][] che memorizzi la distanza più breve dalla cella di partenza fino a quella corrente.Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB