HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Recursion > problem:


50370 - Number of rectangles in a matrix

Guest
• Discussion of problem (1)

Section problems

• 50723 - Tribonacci
• 50370 - Number of rectangles i...
• 50475 - Voice advertising
• 50909 - Gold Coins
• 50376 - Sequences
• 50725 - Fibonacci Series
• 50385 - The 3n + 1 problem
• 50911 - Symmetric Array
• 50381 - Sum of the numbers
• 50389 - Reverse an Array

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