HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Recursion > problem:


50370 - Number of rectangles in a matrix

Guest
• Discussion of problem (1)

Section problems

• 50381 - Sum of the numbers
• 51081 - Fish Pond I
• 50935 - Max Discount
• 50724 - Number of Circles
• 50729 - Max number in 2D array
• 50928 - War Of Battleships
• 50577 - Perfect Numbers and Perfec...
• 50725 - Fibonacci Series
• 50370 - Number of rectangles i...
• 50376 - Sequences
• 50421 - Repairing road segments
• 50389 - Reverse an Array
• 50727 - Fibonacci Numbers
• 50726 - Pascal Triangle - 1
• 50475 - Voice advertising
• 50721 - Palindrome

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Difficulty Beta

Number of rectangles in a matrix

Question:
In a piece of paper containing n x m squares, someone drew some rectangles that do not intersect nor touch each other except on the corners. Write a program that prints the numbers of rectangles in the paper.

Express the paper as a matrix A in which

Ai,j = 1

if the square (1,1) belongs to some rectangle, and

Ai,j = 0

otherwise.

Input specification
In the first line you will be given two integers n (number of rows) and m (number of columns) where 1 ≤ n, m ≤ 30
The followint n lines contain m numbers (1 or 0) each.

Output specification
Show just one integer number: the number of rectangles in the matrix.

Sample Input I   
  10 10
  0 0 0 1 1 1 0 0 1 1   
  0 0 0 1 1 1 0 0 1 1   
  0 0 0 1 1 1 0 0 0 0   
  0 1 1 0 0 0 0 0 0 0   
  0 1 1 0 0 0 0 1 1 1   
  0 1 1 0 1 1 0 0 0 0   
  0 1 1 0 1 1 0 0 0 0   
  0 0 0 0 0 0 1 0 1 0   
  0 0 0 0 0 0 0 0 0 0   
  1 1 0 0 0 0 0 0 0 0   
Sample Output I   
  8


Для отправки решений необходимо выполнить вход.

www.contester.ru