uCoder | 1323 | Nível: 5 | Tempo Limite: 6
Mario
Adaptado por Erich Rodrigues
Competição: Interfatecs 2017 1ª Fase
A maioria dos competidores de programação já jogou ou pelo menos ouviu falar do clássico Super Mario Bros. Para aqueles que não conhecem, o jogo tem como foco principal a saga do herói Mario para salvar a princesa Peach das garras do vilão Bowser.
Na aventura de hoje, Mario mais uma vez se dirigia para enfrentar Bowser, quando acabou caindo em uma caverna subterrânea. Para sair dessa caverna e prosseguir sua jornada, Mario precisa encontrar um tubo que o transporte de volta a superfície. Mas para complicar a vida do nosso herói, devido à alta temperatura do local, durante sua caminhada dentro da caverna, ele perde energia.
A energia do nosso herói, como muitos devem saber, é medida por vidas. A cada movimento dentro da caverna, nosso herói perde um quarto de uma vida. Nosso herói pode se movimentar apenas para as células vizinhas que não contenham obstáculos e nas direções horizontal e vertical. Ele não pode se mover na diagonal ou para alguma célula com obstáculo. Sendo assim, a cada 4 células percorridas, nosso herói perde uma vida completa.
Dada a quantidade de vidas do nosso herói e o mapa da caverna, queremos saber se é possível que Mario alcance um tubo antes que suas vidas cheguem a zero. Lembrando que caso ele consiga chegar a um tubo no movimento que o faria perder a última vida, ele milagrosamente consegue escapar.
Entrada
A entrada é composta por uma linha contendo dois inteiros H e W (1 ≤ H, W ≤ 1000), indicando a altura e largura do mapa da caverna. As próximas H linhas contém W caracteres cada, representando o mapa da caverna. O mapa da caverna é representado por H x W células contendo os seguintes caracteres:
• ’.’ representa uma célula livre na caverna, onde Mario pode movimentar;
• ’x’ representa um obstáculo na caverna, onde Mario não pode acessar;
• ’S’ representa a posição inicial do Mario, ao cair na caverna; aparece uma única vez em todo o mapa;
• ’T’ representa um tubo, por onde Mario pode escapar da caverna.
Por fim, após as H linhas, há uma linha contendo um inteiro C(0 ≤ C ≤ 2000), indicando o número de vidas de Mario ao cair na caverna.
Saída
Você deve imprimir a palavra SIM se é possível Mario escapar da caverna e NAO caso não seja possível que ele escape. Finalize com uma quebra de linha.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 2 |
NAO |
|
1 6 |
NAO |
|
1 6 |
SIM |