Count Submatrices With All Ones
Given an m x n binary matrix mat, return the number of submatrices that have all ones.
Example 1
1 0 1 1 1 0 1 1 0
Input
mat = [[1,0,1],[1,1,0],[1,1,0]]Output
13The all-one rectangles include 6 of size 1x1, 2 of size 1x2, 3 of size 2x1, 1 of size 2x2, and 1 of size 3x1, for a total of 13.
Example 2
0 1 1 0 0 1 1 1 1 1 1 0
Input
mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]Output
24The all-one rectangles include 8 of size 1x1, 5 of size 1x2, 2 of size 1x3, 4 of size 2x1, 2 of size 2x2, 2 of size 3x1, and 1 of size 3x2, for a total of 24.
Constraints
- 1 <= m, n <= 150
- mat[i][j] is either 0 or 1.