Camino más corto en una cuadrícula
Dado un laberinto representado como una cuadrícula de r filas y c columnas, se te pide encontrar la longitud del camino más corto desde la celda de inicio hasta la celda final.
La representación del laberinto es la siguiente:
- El suelo se representa con un punto (
.).
- Las paredes se representan con el símbolo (
#).
- El punto de inicio se marca con la letra mayúscula
S.
- La celda final se marca con la letra mayúscula
E.
Puedes moverte entre dos celdas adyacentes (izquierda, derecha, arriba o abajo) siempre que no sean paredes.
El objetivo es encontrar la longitud del camino más corto entre la celda de inicio y la celda final.
Entrada
La primera línea de la entrada contiene dos números enteros
r y c (1 ≤ r, c ≤ 1000).Las siguientes
r líneas contienen c columnas de caracteres que representan la cuadrícula. Cada celda puede ser suelo (.), pared (#), punto de inicio (S) o punto final (E). Se garantiza que en toda la cuadrícula hay exactamente una única S y una única E.Salida
El programa debe mostrar la longitud del camino más corto desde
S hasta E. Si no existe un camino que conecte S con E, el programa debe imprimir Impossible.Ejemplos
Entrada
5 8
########
##.S....
....#.#.
#......#
...#...ESalida
7Tip
No siempre es necesario construir un grafo explícito para ejecutar un algoritmo BFS. A veces, puedes usar grafos implícitos en forma de cuadrículas y aun así implementar BFS sobre ellas.
Hint
Puedes tratar la cuadrícula como tu grafo y utilizar un arreglo bidimensional de distancias
d[][] para representar la distancia más corta desde la celda de inicio hasta cada celda.Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB