1504. Count Submatrices With All Ones Medium

1/**
2 * [1504] Count Submatrices With All Ones
3 *
4 * Given an m x n binary matrix mat, return the number of submatrices that have all ones.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones1-grid.jpg" style="width: 244px; height: 245px;" />
8 * Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
9 * Output: 13
10 * Explanation: 
11 * There are 6 rectangles of side 1x1.
12 * There are 2 rectangles of side 1x2.
13 * There are 3 rectangles of side 2x1.
14 * There is 1 rectangle of side 2x2. 
15 * There is 1 rectangle of side 3x1.
16 * Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
17 * 
18 * Example 2:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones2-grid.jpg" style="width: 324px; height: 245px;" />
20 * Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
21 * Output: 24
22 * Explanation: 
23 * There are 8 rectangles of side 1x1.
24 * There are 5 rectangles of side 1x2.
25 * There are 2 rectangles of side 1x3. 
26 * There are 4 rectangles of side 2x1.
27 * There are 2 rectangles of side 2x2. 
28 * There are 2 rectangles of side 3x1. 
29 * There is 1 rectangle of side 3x2. 
30 * Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= m, n <= 150
36 * 	mat[i][j] is either 0 or 1.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/count-submatrices-with-all-ones/
42// discuss: https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
48        0
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_1504() {
60    }
61}
62