3070. Count Submatrices with Top-Left Element and Sum Less Than k Medium

1/**
2 * [3070] Count Submatrices with Top-Left Element and Sum Less Than k
3 *
4 * You are given a 0-indexed integer matrix grid and an integer k.
5 * Return the number of <span data-keyword="submatrix">submatrices</span> that contain the top-left element of the grid, and have a sum less than or equal to k.
6 *  
7 * <strong class="example">Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2024/01/01/example1.png" style="padding: 10px; background: #fff; border-radius: .5rem;" />
9 * Input: grid = [[7,6,3],[6,6,1]], k = 18
10 * Output: 4
11 * Explanation: There are only 4 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 18.
12 * <strong class="example">Example 2:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2024/01/01/example21.png" style="padding: 10px; background: #fff; border-radius: .5rem;" />
14 * Input: grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
15 * Output: 6
16 * Explanation: There are only 6 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 20.
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	m == grid.length 
22 * 	n == grid[i].length
23 * 	1 <= n, m <= 1000 
24 * 	0 <= grid[i][j] <= 1000
25 * 	1 <= k <= 10^9
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/
31// discuss: https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {
37        0
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_3070() {
49    }
50}
51