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

Nome do arquivo: mancha.x, onde x deve ser c, cpp, java, js ou py

Mancha

Juninho está participando de um projeto de iniciação científica sobre identificação de doenças de pele através de análises de imagens digitais. Muitas vezes o formato de uma lesão de pele, ou mancha, pode indicar as possibilidades de diagnóstico. O professor orientador tem algumas imagens digitalizadas de manchas e precisa identificar aquelas que são "regulares" segundo uma definição bastante precisa, que será dada abaixo. Juninho precisa da sua ajuda para processar a imagem da mancha e decidir se ela é ou não regular.

A imagem é um reticulado de N x N pixels. Os pixels escuros representam a mancha, que é sempre conexa, ou seja, é composta de apenas uma componente. De forma mais precisa, dado qualquer par de pixels pertencentes à mancha, sempre existe um caminho, uma sequência de pixels escuros entre eles seguindo somente por direções ortogonais, totalmente contido dentro da mancha. A figura acima ilustra três possíveis manchas, para N=10.

Dados dois pixels P e Q, a distância de Manhattan entre eles é definida como: d_manhattan(P,Q)=|Pl-Ql|+|Pc-Qc|, onde Pl é o índice da linha do pixel P e Pc é o índice da coluna do pixel P, na imagem digitalizada. O mesmo vale para Ql e Qc. Ou seja, a distância de Manhattan é a soma da diferença absoluta entre a linha de P e a linha de Q com a diferença absoluta entre as colunas de P e Q. Dados dois pixels P e Q que pertencem à mancha, definiremos d(P,Q> como sendo o comprimento do menor caminho existente entre P e Q, que esteja totalmente contido dentro da mancha.

No exemplo da figura mais à esquerda, onde P e Q estão representados por um pequeno círculo, d(P,Q>=9 e d_manhattan(P,Q)=9. Na figura do meio, d(P,Q>=10 e d_manhattan(P,Q)=6; e na figura mais à direita, d(P,Q>=5 e d_manhattan(P,Q)=3.

Finalmente, uma mancha será regular se, para qualquer par de pixels P e Q pertencentes à mancha, tivermos d(P,Q>=d_manhattan(P,Q). Dessa forma, verifique que a figura mais à esquerda ilustra uma mancha regular, enquanto que as outras duas são irregulares.

Entrada

A primeira linha da entrada contém um inteiro N, representando as dimensões da imagem. As N linhas seguintes contêm, cada uma, uma cadeia de N caracteres definindo uma linha de pixels da imagem. Os caracteres podem ser: "." para pixels fora da mancha; e "*" para pixels que pertencem à mancha.

Saída

Imprima uma linha contendo o caractere "S", se a mancha for regular; ou "N", se for irregular.

Restrições

  • 2 ≤ N ≤ 1000;
  • A mancha possui pelo menos dois pixels.

Informações sobre a pontuação

  • Para um conjunto de casos de teste valendo 20 pontos, N ≤ 20;
  • Para um conjunto de casos de teste valendo 40 pontos, N ≤ 100.

Exemplos

Entrada
10
..........
.....*....
...***....
..*****...
..*****...
..*******.
.********.
...*****..
......**..
..........
Saída
S
	

 

Entrada
10
..........
....*.***.
....*.***.
..******..
..****....
....**....
....****..
...*****..
.......*..
..........
Saída
N
	

 

Entrada
2
.*
**
Saída
S
	

 

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