Descrição
Joãozinho está fazendo um curso de extensão em programação de jogos na Fatec Mogi, que tem como trabalho final o projeto e a implementação de um jogo qualquer. Para matar a saudade dos primeiros jogos tridimensionais que jogou, ele optou por criar uma réplica do jogo Wolfenstein 3D.
Este é um jogo de tiro em primeira pessoa no qual o jogador anda e corre por um cenário, composto principalmente por corredores, e tem que eliminar os inimigos que encontra pelo caminho. Após implementar a parte gráfica e de interação do jogo, Joãozinho deseja criar um algoritmo para que os inimigos que estejam dentro de um raio máximo de distância do jogador, quando este atirar, se dirijam até a posição onde ele se encontra para interceptá-lo.
A Figura 1 ilustra uma fase do jogo, onde um 'X' representa uma parede, o sinal ':' representa o jogador, um '*' representa um inimigo, e um espaço vazio ' ' representa um corredor por onde o jogador ou os inimigos podem passar.
Figura 1: Exemplo de fase do jogo com o jogador e quatro inimigos.
Na implementação feita por Joãozinho, a fase é vista como uma parte do quadrante superior direito de um plano cartesiano, com o canto inferior esquerdo em (0,0). Assim, no exemplo apresentado, o jogador está em (3,6) e os inimigos estão em (10,6), (11,4), (12,1) e (24,2). Antes de definir o caminho que o inimigo seguirá para chegar ao jogador, Joãozinho precisa da sua ajuda para definir se há algum caminho entre o jogador e qualquer inimigo que esteja no máximo a uma distância R dele.
Entrada
A entrada é composta por vários casos de teste. A primeira linha de cada caso de teste define dois números inteiros L (0 < L < 50) e C (0 < C < 50), separados por um espaço em branco, representando o número de linhas e colunas da fase do jogo respectivamente. As próximas L linhas contêm C colunas com um dos seguintes caracteres cada: 'X' (parede), ' ' (espaço livre), ':' (jogador) ou '*' (inimigo). A última linha do caso de teste informa um raio R inteiro (R > 0), representado em unidades do plano cartesiano, dentro do qual um tiro do jogador é ouvido pelos inimigos. Em outras palavras, caso a distância no plano entre o jogador e o inimigo seja menor ou igual a R, este pode ouvir um tiro dado pelo jogador.
Saída
Para cada caso de teste, você deve imprimir um caractere 'S', sem aspas e maiúsculo, caso algum inimigo dentro do raio R especificado (<= R) consiga chegar até o jogador por meio de um corredor. Caso não seja possível, imprima 'N', sem aspas e maiúsculo. É importante notar que um inimigo pode passar por qualquer caminho que não seja uma parede, inclusive por um caminho onde se encontra outro inimigo, mas ela só caminha na horizontal e na vertical, nunca na diagonal. Além disso, inimigos podem estar em corredores sem saída.
Para o exemplo apresentado anteriormente, caso o raio R fosse igual a 7 (R = 7), o inimigo da casa (10,6) ouviria o tiro. Como existe um caminho que o leva até o jogador – descer até (10,4), ir para a direita até (20,4), descer até (20,1), ir para a esquerda até (7,1), subir até (7, 6), ir para a esquerda até (3,6) -, a resposta seria 'S'.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
8 30 |
S |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Leandro Luque (Fatec Mogi das Cruzes) | Adaptado por erich.rodriguesf | Competição: Interfatecs 2014 2ª fase