2132. Stamping the Grid Hard

1/**
2 * [2132] Stamping the Grid
3 *
4 * You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).
5 * You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements:
6 * <ol>
7 * 	Cover all the empty cells.
8 * 	Do not cover any of the occupied cells.
9 * 	We can put as many stamps as we want.
10 * 	Stamps can overlap with each other.
11 * 	Stamps are not allowed to be rotated.
12 * 	Stamps must stay completely inside the grid.
13 * </ol>
14 * Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.
15 *  
16 * Example 1:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex1.png" style="width: 180px; height: 237px;" />
18 * Input: grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
19 * Output: true
20 * Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.
21 * 
22 * Example 2:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex2.png" style="width: 170px; height: 179px;" />
24 * Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
25 * Output: false 
26 * Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	m == grid.length
32 * 	n == grid[r].length
33 * 	1 <= m, n <= 10^5
34 * 	1 <= m * n <= 2 * 10^5
35 * 	grid[r][c] is either 0 or 1.
36 * 	1 <= stampHeight, stampWidth <= 10^5
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/stamping-the-grid/
42// discuss: https://leetcode.com/problems/stamping-the-grid/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn possible_to_stamp(grid: Vec<Vec<i32>>, stamp_height: i32, stamp_width: i32) -> bool {
48        false
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_2132() {
60    }
61}
62