Manchas de pele
O laboratório de dermatologia da Linearlândia está implementando um
software para contar o número de manchas presentes numa imagem digital
de N por M pixels. Cada pixel na imagem é preto ou branco e dois
pixels pretos distintos A e B pertencem à mesma mancha se e somente
se: existir uma sequência de pixels
[P1,P2,...,Pk], onde k ≥ 2,
A=P1, B=Pk e para todo 1 ≤ ii é ortogonalmente adjacente a Pi+1
(Pi imediatamente acima, abaixo, à esquerda ou à direita de
Pi+1).
A figura acima, para N=8 e M=9, ilustra uma imagem digital onde existem
oito manchas. Dada a imagem, seu programa deve contar o número de manchas
presentes.
Entrada
A primeira linha da entrada contém dois inteiros N e M, representando,
respectivamente, o número de linhas e colunas da imagem. As N linhas seguintes contêm,
cada uma, M inteiros P representando os pixels da imagem.
Saída
Seu programa deve imprimir uma linha contendo um inteiro, o número de manchas na imagem.
Restrições
- 1 ≤ N ≤ 1000
- 1 ≤ M ≤ 1000
- O valor de P é 1, representando um pixel preto, ou 0, representando um pixel branco.
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 10 pontos, N=M=2.
- Para um conjunto de casos de testes valendo outros 20 pontos, N=1.
- Para um conjunto de casos de testes valendo outros 20 pontos, N,M ≤ 100.
- Para um conjunto de casos de testes valendo outros 50 pontos,
nenhuma restrição adicional ( Atenção, para essa parcial, não é recomendada uma implementação recursiva!)
Exemplos
Entrada
8 9
1 0 0 0 0 0 1 1 1
1 1 0 1 1 1 0 1 1
1 0 0 0 0 1 0 1 0
0 0 1 0 0 1 1 1 0
0 1 1 0 0 0 0 1 0
0 1 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0 1
1 1 1 0 0 0 0 1 0
|
Saída
8
|
Entrada
1 10
0 0 1 0 1 1 1 0 1 0
|
Saída
3
|