2290. Minimum Obstacle Removal to Reach Corner Hard

1/**
2 * [2290] Minimum Obstacle Removal to Reach Corner
3 *
4 * You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
5 * 
6 * 	0 represents an empty cell,
7 * 	1 represents an obstacle that may be removed.
8 * 
9 * You can move up, down, left, or right from and to an empty cell.
10 * Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png" style="width: 605px; height: 246px;" />
14 * Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
15 * Output: 2
16 * Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
17 * It can be shown that we need to remove at least 2 obstacles, so we return 2.
18 * Note that there may be other ways to remove 2 obstacles to create a path.
19 * 
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png" style="width: 405px; height: 246px;" />
22 * Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
23 * Output: 0
24 * Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	m == grid.length
30 * 	n == grid[i].length
31 * 	1 <= m, n <= 10^5
32 * 	2 <= m * n <= 10^5
33 * 	grid[i][j] is either 0 or 1.
34 * 	grid[0][0] == grid[m - 1][n - 1] == 0
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/
40// discuss: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn minimum_obstacles(grid: Vec<Vec<i32>>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_2290() {
58    }
59}
60