1293. Shortest Path in a Grid with Obstacles Elimination

leetcode_1293.md

Description

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.

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.

Link to the original problem

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).

Constraints:

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

Idea

1. First when I see this question, I tend to think of the easier version of it, that is, if there are no obstacles, what is the solution?
2. Actually that is not too hard, since we can move only in horizontal or vertical directions, the shortest path is to move to the rightmost first and then to the bottom, or vice versa. That gives us M + N - 2, M being the number of rows, and N being the number of columns.
3. However, you might ask, "There are gonna be obstacles, so the logic here is not that much helpful?".
4. Yep, you are right. The obstacles can change the path dramatically in a way that sometimes we might even have to go "backwards" to just bypass some obstacles.
5. Although that's 100% true, it still give us some insights about the solution, because we have the power to remove the obstacles! Wow, that sounds really cool, only thing is that we can only remove k of them.
6. So suppose we can remove all the obstacles in our "ideal shortest" path, we can just remove them and this is one edge case or "shortcut"!
7. Alright, let's get a little bit more serious. So there're more obstacles than we can remove in the matrix, what do we do?
8. Suppose you are standing on one of the cells in the matrix now, what information do you think you need to get the destination?
9. Well, I can think of something like, "how many steps I have tried so far to get here", or "can I keep removing obstacles if there're in front of me", or "am I already at the destination"?
10. So these are all valuable information. For example, we need to know our current location to know if we have already reached the destination, and we need to know how many obstacles we can still remove to keep removing them.
11. So we need some sort of state (current location, # of obstacles we can remove).
12. Well, you might ask, "What about the current steps we have taken so far"?
13. The steps are a bit special, so we are gonna process it differently. Because if you think about it, it's possible that we might revisit the same cell in the matrix, because 1) you can visit backwards if you want, and 2) you can try to remove or leave the obstacles and you'll follow different paths to get a particular cell. So there're quite a lot of possiblities. So what do we do?
14. So if we can record the (minimum) steps taken to reach each cell, we should be able to make our decisions wisely. An intuitive example is a 3-dimensional array arr[i][j][k], which means "minimum steps taken to reach cell [i][j]" with the ability to remove k obstacles.
15. At least one thing we can be sure of is that, if we know we can get to cell C with fewer steps, we don't need to try another path if it requires more steps to get C.
16. Wait, "I think there's still something missing here, like if we get to a certain cell C with fewer steps but it requires more obstacles to remove, it does not necessarily mean it's the best solution, because you might won't get the destination because you cannot remove more obstacles. Doesn't it matter?", you might ask.
17. That's an excellent question! So we do need somehow to guarantee that when we reach the destination we use minimum steps.
18. How though? There enters BFS. The general idea is that for each step i, we try all possibilities and the results of step i will become the input of next step i+1. Because we try all possibilities for each step, we can make sure that when we reach the destination, it's the global minimum steps.
19. Luckily we can save some computation in a way that we only keep trying path reaching a cell with fewer steps.
20. The code should explain itself.

Solution

Javascript

const shortestPath = function(grid, k) {
  const M = grid.length, N = grid[0].length;
  if (k >= M + N - 3) return M + N - 2;

  const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  const isValid = (i, j) => i >= 0 && i < M && j >= 0 && j < N;

  // dp[i][j][k]: min steps to reach grid[i][j] with k obstacles available to remove
  const dp = [...Array(M)].map(_ => [...Array(N)].map(_ => Array(k+1).fill(Infinity)));
  dp[0][0][k] = 0;

  // [[x coordinate, y coordinate], # of obstacles left can remove]
  const queue = [[[0, 0], k]];
  while (queue.length) {
    const [[x, y], remain] = queue.shift();
    if (x == M - 1 && y == N - 1) return dp[x][y][remain];
    for (const [dx, dy] of DIRS) {
      const nx = x + dx, ny = y + dy;
      if (!isValid(nx, ny)) continue;
      const left = remain - grid[nx][ny];
      if (left >= 0 && dp[x][y][remain] + 1 < dp[nx][ny][left]) {
        dp[nx][ny][left] = dp[x][y][remain] + 1;
        queue.push([[nx, ny], left]);
      }
    }
  }
  return -1;
};

Python

def shortestPath(self, grid: List[List[int]], k: int) -> int:
    M, N = len(grid), len(grid[0])
    if k >= M + N - 3:
        return M + N - 2

    DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    def isValid(i, j):
        return i >= 0 and i < M and j >= 0 and j < N

    # dp[i][j][k]: min steps to reach grid[i][j] with k obstacles available to remove
    dp = [[[M * N for k in range(k+1)] for _ in range(N)] for _ in range(M)]
    dp[0][0][k] = 0

    # [[x coordinate, y coordinate], # of obstacles left can remove]
    dq = collections.deque([[0, 0, k]])
    while dq:
        [x, y, remain] = dq.popleft()
        if x == M - 1 and y == N - 1:
            return dp[x][y][remain]
        for [dx, dy] in DIRS:
            nx, ny = x + dx, y + dy
            if not isValid(nx, ny):
                continue
            left = remain - grid[nx][ny]
            if left >= 0 and dp[x][y][remain] + 1 < dp[nx][ny][left]:
                dp[nx][ny][left] = dp[x][y][remain] + 1
                dq.append([nx, ny, left])
    return -1