Caminho Mais Curto em uma Grelha
Dado um labirinto representado como uma grelha de r linhas por c colunas, é solicitado que se encontre o comprimento do caminho mais curto desde a célula inicial até a célula final.
O labirinto é representado da seguinte forma:
O piso é um ponto (
.).As paredes são cerquilhas (
#).O ponto de partida é a letra maiúscula
S.O ponto final é a letra maiúscula
E.
É possível deslocar-se para células adjacentes (esquerda, direita, cima ou baixo) se elas não forem paredes.
O objetivo é determinar o comprimento do caminho mais curto entre a célula inicial e a célula final.
Entrada
A primeira linha da entrada contém dois inteiros r e c (1 ≤ r, c ≤ 1000).
As próximas r linhas contêm c colunas de caracteres que representam a grelha. Cada célula pode ser piso (.), parede (#), ponto de partida (S) ou ponto final (E). Garante-se que exista exatamente um S e um E em toda a grelha.
Saída
O programa deve imprimir o comprimento do caminho mais curto de S até E. Caso seja impossível chegar de S a E, deve-se imprimir Impossible.
Exemplos
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Dica
Nem sempre é necessário construir um grafo explicitamente para executar um algoritmo de BFS. Às vezes, basta tratar a grelha como um grafo implícito e fazer a busca nela diretamente.
Sugestão
Você pode tratar a grelha como o seu grafo e manter um array bidimensional de distâncias d[][], que representa a menor distância entre a célula inicial e cada uma das restantes.
Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB