4 - Dungeon Master 

Você está preso em um calabouço 3D e precisa encontrar a maneira mais rápida de sair! O calabouço é composto de cubos unitários podem ou não estar preenchidos com rochas. Leva um minuto para mover-se uma unidade ao norte, sul, leste, oeste, para cima, ou para baixo. Você não pode ser mover na diagonal, e o labirinto é certado de rochas sólidas em todos os lados.

É possível escapar? Se sim, quanto tempo levará?

Entrada

O arquivo de entrada consiste de vários calabouços. A descrição de cada um deles começa com uma linha contendo três inteiros, N, L e C (todos limitados a tamanho 30).

N é o número de níveis que compõem o calabouço.

L e C são os números de linhas e colunas do plano de cada nível.

Em seguida estarão N blocos de L linhas, cada uma contendo C caracteres. Cada caracter descreve uma célula do calabouço. Uma célula preenchida de rochas é indicada por um `#' e células vazias são representacas por `.'. Sua posição inicial é indicada por um `I' e a saída por um 'S'. Há uma linha em branco após cada nível. A entrada termina quando N, L e C forem zero.

Saída

Cada labirinto gera uma linha de saída. Se for possível encontrar uma saída, imprima uma linha na forma:

Escapou em x minuto(s).

onde x corresponde ao menor tempo necessário para escapar. Se não for possível escapar, imprima a linha:

Preso!

Entrada Exemplo 

3 4 5
I....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####S

1 3 3
I##
#S#
###

0 0 0

Saída Exemplo

Escapou em 11 minuto(s).
Preso!