1074. Number of Submatrices That Sum to Target Hard

1/**
2 * [1074] Number of Submatrices That Sum to Target
3 *
4 * Given a matrix and a target, return the number of non-empty submatrices that sum to <font face="monospace">target</font>.
5 * A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.
6 * Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg" style="width: 242px; height: 242px;" />
10 * Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
11 * Output: 4
12 * Explanation: The four 1x1 submatrices that only contain 0.
13 * 
14 * Example 2:
15 * 
16 * Input: matrix = [[1,-1],[-1,1]], target = 0
17 * Output: 5
18 * Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
19 * 
20 * Example 3:
21 * 
22 * Input: matrix = [[904]], target = 0
23 * Output: 0
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	1 <= matrix.length <= 100
29 * 	1 <= matrix[0].length <= 100
30 * 	-1000 <= matrix[i] <= 1000
31 * 	-10^8 <= target <= 10^8
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
37// discuss: https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_1074() {
55    }
56}
57