Given a N*M matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input:
N = 3
M = 4
matrix [ ][ ] =
[ [0, 1, 1, 1],
[1, 1, 1, 1],
[0, 1, 1, 1] ]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There are 1 squares of side 3.
Total number of squares = 10 + 4 + 1 =15

Example 2:
Input:
N = 3
M = 3
matrix [ ][ ] =
[ [1, 0, 1],
[1, 1, 0],
[1, 1, 0] ]
Output: 7
Explanation:
There are 6 squares of side 1.
There are 1 squares of side 2.
Total number of squares = 6 + 1 =7

Your Task:
You don't need to read input or print anything. Your task is to complete the function countSquares() which takes the interger N, integer M and 2D integer array matrix[ ][ ] as parameters and returns the number of square submatrices have all ones.
Expected Time Complexity: O(NM)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N,M ≤ 310^{3}
0 ≤ matrix [ i ][ j ] ≤ 1

见题面

见题面