28a Olimpíada Brasileira de Informática
Submeta sua solução

Câmeras

Uma exposição vai ser montada num espaço retangular, dividido em N × M células dispostas em N colunas por M linhas. Uma célula é o espaço delimitado pela interseção de uma coluna com uma linha. As colunas estão na direção Norte-Sul e as linhas na direção Oeste-Leste. Para segurança das obras foram instaladas K câmeras, em células selecionadas. Cada câmera pode estar apontada para uma de quatro direções: Norte, Sul, Leste ou Oeste. Uma câmera observa todas as células da coluna ou linha na direção em que está apontada, a partir da célula em que está instalada (incluindo a célula em que está instalada). A porta de entrada da exposição está na célula mais ao norte e mais à oeste, a porta de saída está na célula mais ao sul e mais ao leste. A figura abaixo ilustra um espaço de exposição com 6 colunas, 5 linhas e 5 câmeras instaladas.
Preocupado com a segurança, o organizador da exposição deseja saber se é possível que um visitante entre pela porta de entrada e saia pela porta de saída, movendo-se somente nas quatro direções (Norte, Sul, Leste ou Oeste) sem que seja observado por qualquer das câmeras instaladas.

Entrada

A primeira linha contém três inteiros N, M e K indicando respectivamente o número de colunas, o número de linhas e o número de câmeras instaladas. As colunas estão numeradas de 1 a N e as linhas estão numeradas de 1 a M. A coluna 1 é a coluna mais à Oeste e a linha 1 é a linha mais ao Norte. Cada uma das K linhas seguintes descreve uma câmera e contém dois inteiros Ci, Li e um caractere Di, indicando respectivamente a coluna, a linha e a direção em que a câmera está instalada. O caractere Di pode ser N, S, L ou O, indicando respectivamente que a câmera está instalada direcionada para o Norte, Sul, Leste ou Oeste.

Saída

Seu programa deve produzir uma única linha, contendo um único caractere, que deve ser S se é possível que um visitante entre pela porta de entrada e saia pela porta de saída sem que seja observado por qualquer das câmeras instaladas, ou N caso contrário.

Restrições

  • 2 ≤ N ≤ 30; 2 ≤ M ≤ 30; 1 ≤ K ≤ 30
  • 1 ≤ Ci ≤ N, para 1 ≤ i ≤ K
  • 1 ≤ Li ≤ M, para 1 ≤ i ≤ K
  • Di pode ser N, S, L ou O.

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 10 pontos, M = 2 e K = 1.
  • Para um conjunto de casos de testes valendo outros 10 pontos, N = 3, M = 3 e K = 2.
  • Para um conjunto de casos de testes valendo outros 80 pontos, nenhuma restrição adicional.

Exemplos

Entrada
4 5 2
2 2 O
3 3 L
Saída
N
	

 

Entrada
5 4 2
2 3 N
4 2 S
Saída
S
	

 

Entrada
6 5 5
1 2 S
3 2 N
5 2 N
3 4 O
5 4 L
Saída
S
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação