Hard

题目描述

给你一个下标从 0 开始的二维整数数组 grid，数组大小为 m x n。每个单元格都是下面两个值之一：

  • 0 表示一个 空 单元格，
  • 1 表示一个可以被移除的 障碍 。

你可以向 上、下、左、右 移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍的 最小数目 。

示例 1：

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]
输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除 2 个障碍，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍，创建出可行的路径。

示例 2：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出：0
解释：不移除任何障碍就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • grid[i][j] 是 0 或 1
  • grid[0][0] == grid[m - 1][n - 1] == 0

解题思路

这道题本质上是一个最短路径问题，但边权不是常规的 1，而是根据移动到的格子类型决定：

  • 移动到空格子（值为 0）：代价为 0
  • 移动到障碍格子（值为 1）：代价为 1（需要移除障碍）

可以用以下几种方法求解：

方法一：0-1 BFS（双端队列） 由于边权只有 0 和 1，可以使用 0-1 BFS。使用双端队列，当移动代价为 0 时从队头加入，代价为 1 时从队尾加入，保证队列中距离单调递增。

方法二：Dijkstra 算法 将网格建模为图，使用 Dijkstra 算法求最短路径。每个格子是节点，相邻格子间有边，边权为目标格子的值。

方法三：动态规划 + BFS 也可以用 BFS 配合距离数组，但效率不如前两种方法。

推荐使用 0-1 BFS，因为它专门针对边权为 0 和 1 的图设计，时间复杂度更优。基本思路是：从起点开始，优先处理代价为 0 的移动（加入队头），再处理代价为 1 的移动（加入队尾），直到到达终点。

代码实现

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        deque<pair<int, int>> dq;
        
        dist[0][0] = 0;
        dq.push_back({0, 0});
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!dq.empty()) {
            auto [x, y] = dq.front();
            dq.pop_front();
            
            if (x == m - 1 && y == n - 1) {
                return dist[x][y];
            }
            
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newDist = dist[x][y] + grid[nx][ny];
                    if (newDist < dist[nx][ny]) {
                        dist[nx][ny] = newDist;
                        if (grid[nx][ny] == 0) {
                            dq.push_front({nx, ny});
                        } else {
                            dq.push_back({nx, ny});
                        }
                    }
                }
            }
        }
        
        return dist[m-1][n-1];
    }
};

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        from collections import deque
        
        m, n = len(grid), len(grid[0])
        dist = [[float('inf')] * n for _ in range(m)]
        dq = deque([(0, 0)])
        dist[0][0] = 0
        
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while dq:
            x, y = dq.popleft()
            
            if x == m - 1 and y == n - 1:
                return dist[x][y]
            
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    new_dist = dist[x][y] + grid[nx][ny]
                    if new_dist < dist[nx][ny]:
                        dist[nx][ny] = new_dist
                        if grid[nx][ny] == 0:
                            dq.appendleft((nx, ny))
                        else:
                            dq.append((nx, ny))
        
        return dist[m-1][n-1]

public class Solution {
    public int MinimumObstacles(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,] dist = new int[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = int.MaxValue;
            }
        }
        
        var deque = new LinkedList<(int, int)>();
        dist[0, 0] = 0;
        deque.AddLast((0, 0));
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (deque.Count > 0) {
            var (x, y) = deque.First.Value;
            deque.RemoveFirst();
            
            if (x == m - 1 && y == n - 1) {
                return dist[x, y];
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i, 0];
                int ny = y + dirs[i, 1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newDist = dist[x, y] + grid[nx][ny];
                    if (newDist < dist[nx, ny]) {
                        dist[nx, ny] = newDist;
                        if (grid[nx][ny] == 0) {
                            deque.AddFirst((nx, ny));
                        } else {
                            deque.AddLast((nx, ny));
                        }
                    }
                }
            }
        }
        
        return dist[m-1, n-1];
    }
}

var minimumObstacles = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    const deque = [[0, 0, 0]];
    const visited = new Set();
    visited.add('0,0');
    
    while (deque.length > 0) {
        const [row, col, obstacles] = deque.shift();
        
        if (row === m - 1 && col === n - 1) {
            return obstacles;
        }
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = `${newRow},${newCol}`;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited.has(key)) {
                visited.add(key);
                
                if (grid[newRow][newCol] === 0) {
                    deque.unshift([newRow, newCol, obstacles]);
                } else {
                    deque.push([newRow, newCol, obstacles + 1]);
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型0-1 BFSDijkstra
时间复杂度O(mn)O(mn log(mn))
空间复杂度O(mn)O(mn)

其中 m 和 n 分别是网格的行数和列数。0-1 BFS 的时间复杂度更优，因为每个节点最多被访问两次（一次作为 0 边，一次作为 1 边），而 Dijkstra 需要使用优先队列维护最小距离。

相关题目