28a Olimpíada Brasileira de Informática
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.
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 |