uCoder | 1182 | Nível: 4 | Tempo Limite: 6
Pacman
Adaptado por erich.rodriguesf
Competição: Interfatecs 2015
Pacman é um famoso jogo, criado pela Namco para fliperamas, que teve versões para diversos consoles, como Game Boy e Nintendo DS. O jogo consiste em um labirinto onde se encontra o jogador, representado por uma pizza sem uma fatia (essa foi a inspiração real para a personagem), fantasmas, que não podem ser tocados, e itens que devem ser coletados (círculo escuro), conforme Figura 1. Nesta figura, existem dois fantasmas e um item a ser coletado.
Você foi convidado para implementar uma nova versão do jogo onde os labirintos são gerados em tempo de execução (no jogo original, o labirinto era sempre o mesmo) e os fantasmas ficam parados (no jogo original, eles se moviam). Em resumo, o jogo consiste em mover o jogador pelo labirinto, sem tocar nos fantasmas, até coletar o item. Para tanto, você precisa saber se, dado um certo labirinto gerado pelo seu código, existe ao menos um caminho que leva o jogador até o item sem passar por um fantasma.
Entrada
A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém um inteiro N (7 ≤ N ≤ 20), indicando o número N de linhas e colunas do labirinto (incluindo as paredes externas). As próximas N linhas contêm N caracteres C (C=’*’, C=’I’, C=’T’, C=’#’, C=’ ‘) cada representando o labirinto e o seu conteúdo. Um caractere C=’*’ indica uma parede do labirinto. Um caractere C=’I’ indica o local onde se encontra o jogador. Um caractere C=’T’ indica o local onde está o item a ser coletado. Um caractere C=’#’ indica o local onde está um fantasma. Um espaço em branco (C=’ ‘), por sua vez, representa um caminho livre no labirinto. Em um mesmo labirinto, existe apenas um jogador e um item a ser coletado, mas podem existir vários fantasmas. A entrada termina com o fim do arquivo.
Saída
Para cada caso de teste, imprima um caractere ‘S’ (maiúsculo e sem aspas), caso exista ao menos um caminho entre o jogador e o item a ser coletado sem passar por fantasmas. Caso contrário, imprima um caractere ‘N’ (maiúsculo e sem aspas).
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
7 |
S |