Fields P45829


Statement
 

pdf   zip

A rectangular field of size m×nm\times n contains mnmn square areas. Some of the areas are occupied by a determinated growing (tomatoes, carrots, etc.) that is identified by a natural number strictly positive. It is known that growings are grouped in different disjointed rectangles and that a growing always is separated of another one by areas without grownings, identify by the value 0.

Write a program that reads fields and prints the number of rectangular growings.

Input

Input consists in a sequence of fields. For each field, it is given two natural numbers mm and nn with m1m\ge1 and n1n\ge1 that represent the size of the field. Then, it is given mm rows, each one with nn natural numbers that represent the growing of the area. The fields follow the hypotheses described previously.

Output

For each fielf of the input, print in a line the number of rectangular growings.

Public test cases
  • Input

    6 10
    1 1 1 0 3 3 3 0 2 2
    1 1 1 0 3 3 3 0 2 2
    0 0 0 0 3 3 3 0 0 0 
    2 2 0 0 3 3 3 0 4 4
    0 0 0 0 0 0 0 0 0 0
    1 1 1 1 1 0 4 4 4 0
    
    3 3
    0 0 0
    0 9 0
    0 0 0 
    

    Output

    7
    1
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python