Por Brazil
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.
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.
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 |