Count Square Submatrices with All Ones
Given an m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1
0 1 1 1 1 1 1 1 0 1 1 1
Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]Output
15There are 10 squares of side 1, 4 squares of side 2, and 1 square of side 3, for a total of 15 squares.
Example 2
1 0 1 1 1 0 1 1 0
Input
matrix = [[1,0,1],[1,1,0],[1,1,0]]Output
7There are 6 squares of side 1 and 1 square of side 2, for a total of 7 squares.
Constraints
- 1 <= arr.length <= 300
- 1 <= arr[0].length <= 300
- 0 <= arr[i][j] <= 1