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

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

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 1
0
Saída
0
	

 

Entrada
1 10
0 0 1 0 1 1 1 0 1 0
Saída
3
	

 

Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação