Thursday, July 12, 2012

find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately


Given a matrix of order M x N containing 1.s and 0's, you have to find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately. Unit squares (length of side = 1) should be also counted.
Note that squares are filled, i.e. they cannot contain 0.s.

Number of maximal square: 6
Input specification:
The first line consists of integers M and N, the number of rows and columns of the matrix.
0 < M and N <=40
Next M lines contain N characters from the set {0, 1}.
Output specification:
An integer representing the number of maximal squares that can be formed followed by a newline.
Sample Input and Output:

Input:
4 5
11001
11110
11011
11001

Output:
9

Input:
2 2
10
11

Output:
3

Source: Heard From user Bhavesh

No comments :