LeetCode [1293] Shortest Path in a Grid with Obstacles Elimination

 1293. Shortest Path in a Grid with Obstacles Elimination

Hard

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

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.

 

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
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).

 

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

 

Constraints:

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] == 0 or 1
• grid[0][0] == grid[m-1][n-1] == 0

Time Complexity
O(m*n*k) time complexity
This is because for every cell (m*n), in the worst case we have to put that cell into the queue/bfs k times.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public int shortestPath(int[][] grid, int k) { int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int m = grid.length, n = grid[0].length; Queue<int[]> que = new LinkedList<>();//r, c, b int[][] blks = new int[m][n];//min blks to get i, j for(int i=0; i<m; ++i){ Arrays.fill(blks[i], Integer.MAX_VALUE); } blks[0][0] = 0; que.add(new int[]{0,0,0}); int steps = 0; while(!que.isEmpty()){ int sz = que.size(); for(int i=0; i<sz; ++i){ int[] t = que.poll(); int r = t[0], c = t[1], b = t[2]; if(r==m-1 && c==n-1) return steps; for(int[] d : dirs){ int r1 = r+d[0], c1 = c+d[1], b1 = 0; if(r1>=0 && r1<m && c1>=0 && c1<n){ b1 = b + grid[r1][c1]; //blks[m-1][n-1] must be <= k when we reach it && only push [r1][c1] if its blks value decreased if(b1>k || b1>=blks[r1][c1]) continue; blks[r1][c1] = b1; que.add(new int[] {r1, c1, b1}); } } } steps++; } return -1; } }

YMSF

一、输入一二维数组，0是路1是墙，从左上到右下的最少走多少步

follow up，如果能够把一堵墙拆掉，那么从左上到右下最少走多少步