小旭讲解 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/
最后修改日期:2019年12月27日

作者

留言

撰写回覆或留言

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