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