Voltar

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
*******
*  T*I*
* *** *
*   # *
* *** *
*     *
*******

S