1293. Shortest Path in a Grid with Obstacles Elimination Hard

1/**
2 * [1293] Shortest Path in a Grid with Obstacles Elimination
3 *
4 * You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
5 * Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/09/30/short1-grid.jpg" style="width: 244px; height: 405px;" />
9 * Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
10 * Output: 6
11 * Explanation: 
12 * The shortest path without eliminating any obstacle is 10.
13 * The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2021/09/30/short2-grid.jpg" style="width: 244px; height: 245px;" />
17 * Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
18 * Output: -1
19 * Explanation: We need to eliminate at least two obstacles to find such a walk.
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	m == grid.length
25 * 	n == grid[i].length
26 * 	1 <= m, n <= 40
27 * 	1 <= k <= m * n
28 * 	grid[i][j] is either 0 or 1.
29 * 	grid[0][0] == grid[m - 1][n - 1] == 0
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
35// discuss: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn shortest_path(grid: Vec<Vec<i32>>, k: i32) -> i32 {
41        0
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_1293() {
53    }
54}
55