Fields P45829


Statement
 

pdf   zip

thehtml

A rectangular field of size m× n contains mn 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 m and n with m≥1 and n≥1 that represent the size of the field. Then, it is given m rows, each one with n 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