fakeac's blog

By fakeac, history, 8 years ago, In English
You have been given a n*n matrix consisting of 0's and 1's.You need to find the number of squares in the matrix such that it contains no 1's (All entries should be 0).

Constraints:
1=<n<=5000

Input:
First line consists of a single integer n.
Each of the next n lines consist of a binary string of length n.
Output:
Output just one integer, the answer as described above.

Sample:
Input:
3
000
000
000
Output:
14
Explanation: There are 9=> 1 * 1 squares, 4=> 2 * 2 squares and 1=> 3 * 3 square.

Input:
2
10
10
Output:
2
Explanation: There are 2=> 1 * 1 squares. All other squares contain a 1.

Input:
2
11
11
Output:
0

Input:
1
0
Output:
1
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Let pd[i][j] be the number of squares formed with the lower right corner on m[i][j]

if m[i][j] == 1 || i or j out of bounds, pd[i][j] = 0

else pd[i][j] = 1 + min(pd[i-1][j], pd[i][j-1], pd[i-1][j-1])

the answer is the sum of pd[i][j], 1<=i,j<=n. I'm almost sure this is right. The thought is: if you have a 0 on m[i][j] and you have a square k x k on [i-1][j], [i][j-1] and [i-1][j-1], you have a square k+1 x k+1 on m[i][j] too. This is O(n^2), the same complexity as reading the input.