Fuga de Azkaban

Descrição

Um famoso bruxo da Fraternidade dos Conjuradores de Tormentas Espectrais (FCTE) está tentando escapar da prisão mais temida do mundo. A prisão é representada por um mapa de tamanho $N \times M$. A posição inicial é sempre $(1, 1)$ e o ponto de fuga é sempre $(N, M)$.

• . representa um corredor livre.
• # representa uma parede.

Mover-se para uma célula adjacente (cima, baixo, esquerda ou direita) custa 1 minuto.

Determine se é possível para o bruxo alcançar o ponto de fuga dentro do tempo máximo permitido $T$.

Entrada

• A primeira linha contém três inteiros:

  $N$ — o número de linhas do mapa

  $M$ — número de colunas do mapa

  $T$ — tempo máximo

• As próximas $N$ linhas contêm $M$ caracteres cada (. ou #), representando o mapa.

Restrições

• $2 \leq N \leq 500$
• $1 \leq T \leq N \times N$

Saída

• Imprima POSSIVEL se houver um caminho com custo mínimo $\leq T$.
• Imprima NEM A PAU JUVENAL se houver um caminho mas o tempo for maior que $T$.
• Imprima IMPOSSIVEL caso contrário.

Exemplo 1

Entrada

4 4 7
....
.##.
.##.
....

Saída

POSSIVEL

Exemplo 2

5 6 12
......
######
......
.#####
......

Saída

IMPOSSIVEL

Exemplo 2

2 2 1
..
..

Saída

NEM A PAU JUVENAL