URI Online Judge | 3061

Manchas de Pele

Por BR Brazil

Timelimit: 1

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 ≤ i < k, Pi é 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 de Entrada Exemplos de Saída

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

8

1 1

0

0

1 10

0 0 1 0 1 1 1 0 1 0

3