3197. Find the Minimum Area to Cover All Ones II Hard

1/**
2 * [3197] Find the Minimum Area to Cover All Ones II
3 *
4 * You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles.
5 * Return the minimum possible sum of the area of these rectangles.
6 * Note that the rectangles are allowed to touch.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">grid = [[1,0,1],[1,1,1]]</span>
11 * Output: <span class="example-io">5</span>
12 * Explanation:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" />
14 * 
15 * 	The 1's at (0, 0) and (1, 0) are covered by a rectangle of area 2.
16 * 	The 1's at (0, 2) and (1, 2) are covered by a rectangle of area 2.
17 * 	The 1 at (1, 1) is covered by a rectangle of area 1.
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">grid = [[1,0,1,0],[0,1,0,1]]</span>
22 * Output: <span class="example-io">5</span>
23 * Explanation:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" />
25 * 
26 * 	The 1's at (0, 0) and (0, 2) are covered by a rectangle of area 3.
27 * 	The 1 at (1, 1) is covered by a rectangle of area 1.
28 * 	The 1 at (1, 3) is covered by a rectangle of area 1.
29 * </div>
30 *  
31 * Constraints:
32 * 
33 * 	1 <= grid.length, grid[i].length <= 30
34 * 	grid[i][j] is either 0 or 1.
35 * 	The input is generated such that there are at least three 1's in grid.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-ii/
41// discuss: https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-ii/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn minimum_sum(grid: Vec<Vec<i32>>) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_3197() {
59    }
60}
61