1293. Shortest Path in a Grid with Obstacles Elimination

by

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

思路

BFS

使用一个二维数组 visited_with_used_k[m][n] 记录访问 x, y 这个点时最少需要移除几个障碍物。

使用一个队列 q 记录接下来搜索哪些点。每个 push 入队列的点需要带上“访问时移除了几个障碍物”。

  1. 在 BFS 的每个 step 周期开始时，先记录此 step 周期中需要检查多少个点，即此时 q 的 size。
  2. 随后对 q 中的这 size 个元素，依次取出它们检查坐标是否在 grid 的边界内。对于每一个点：
    • 若不在边界内，continue；
    • 若在边界内，但此点有障碍，而已经移除了 >= k 个障碍物（没有剩余的移除机会了），continue；
    • 若之前到访过此点，且只需移除比现在少的障碍物，continue。
  3. 在上述条件过滤后，说明这一点的 visited_with_used_k 有更优值。故更新此值。
  4. 将此点纵横相邻的四个点的坐标 push 入队列。
  5. 若在上述过程中发现到达了 [m - 1][n - 1] 这一点，由于在循环过程中 step 是单增的，故这时的 step 即为所需的最小 step，返回 step。
  6. 若队列中的所有元素都过完了，循环结束仍未到达 [m - 1][n - 1] 这一点，说明无法到达， 返回 -1。
class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        if (m == 0) return -1;
        int n = grid[0].size();
        vector<vector<int>> visited_with_used_k(m, vector<int>(n, INT_MAX));

        std::queue<std::tuple<int, int, int>> q;
        q.emplace(0, 0, 0);
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            
            while (size--) {
                int x, y, used_k;
                tie(x, y, used_k) = q.front();
                if (x == m - 1 && y == n - 1) return step;
                q.pop();

                if (x >= m || x < 0 || y >= n || y < 0) {
                    continue;
                }
                if (grid[x][y] == 1 && used_k >= k) {
                    continue;
                }

                if (grid[x][y] == 1) {
                    used_k++;
                }

                if (visited_with_used_k[x][y] <= used_k) {
                    continue;
                }

                visited_with_used_k[x][y] = used_k;
                q.emplace(x + 1, y , used_k);
                q.emplace(x - 1, y , used_k);
                q.emplace(x, y + 1, used_k);
                q.emplace(x, y - 1, used_k);
            }
            step++;
        }
        
        return -1;
    }
};

Runtime: 24 ms, faster than 77.23% of C++ online submissions for Shortest Path in a Grid with Obstacles Elimination.

Memory Usage: 13.9 MB, less than 67.88% of C++ online submissions for Shortest Path in a Grid with Obstacles Elimination.

Leave a Comment