小旭讲解 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination
小旭讲解 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

BiliBili

YouTube

原题

中文

给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。

English

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)+ 剪枝

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int K) {
        int m = grid.size(), n = grid[0].size();
        if (m == 1 && n == 1) return 0;
        // r,c -> k
        vector<vector<int>> vis(m + 1, vector<int>(n + 1, -1));
        queue<vector<int>> q;
        q.push({0, 0, K});
        vis[0][0] = K;
        
        vector<int> d{0, -1, 0, 1, 0};
        int i = 0, len = q.size(), step = 1;
        while (!q.empty() && i < len) {
            auto node = q.front();
            q.pop();
            for (int di = 0; di < 4; ++di) {
                int nr = node[0] + d[di];
                int nc = node[1] + d[di + 1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                int nk = node[2] - grid[nr][nc];
                if (nk < 0) continue;
                if (vis[nr][nc] >= nk) continue;
                if (nr == m - 1 && nc == n - 1) {
                    return step;
                }
                q.push({nr, nc, nk});
                vis[nr][nc] = nk;
            }
            if (i == len - 1) {
                i = 0;
                len = q.size();
                ++step;
            } else {
                ++i;
            }
        }
        return -1;
    }
};

复杂度分析

  • 时间复杂度:O(m*n*k)
  • 空间复杂度:O(m*n*k)

参考

LeetCode原题:https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-explaination-leetcote-1293-shortest-path-in-a-grid-with-obstacles-elimination/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。