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
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.