到达角落需要移除障碍物的最小数目

难度: 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：

输入：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⁵
2 <= m * n <= 10⁵
grid[i][j] 为 0 或 1
grid[0][0] == grid[m - 1][n - 1] == 0

Submission

运行时间: 691 ms

内存: 41.9 MB

from collections import deque
class Solution:
    def minimumObstacles(self, grid) -> int:
        m = len(grid)
        n = len(grid[0])
        queue = deque()
        queue.append([0,0,0])
        distances = [[900000 for _ in range(n)] for _ in range(m)]
        distances[0][0] = 0
        while len(queue)!=0:
            i,j,k = queue.popleft()
            if i==m-1 and j==n-1:
                return k
            if i>0 and distances[i][j]+grid[i-1][j] < distances[i-1][j]:
                distances[i-1][j] = distances[i][j]+grid[i-1][j]
                if grid[i-1][j]==0:queue.appendleft([i-1,j,k])
                else: queue.append([i-1,j,k+1])
            if i<m-1 and distances[i][j]+grid[i+1][j] < distances[i+1][j]:
                distances[i+1][j] = distances[i][j]+grid[i+1][j]
                if grid[i+1][j]==0:queue.appendleft([i+1,j,k])
                else: queue.append([i+1,j,k+1])
            if j>0 and distances[i][j]+grid[i][j-1] < distances[i][j-1]:
                distances[i][j-1] = distances[i][j] + grid[i][j-1]
                if grid[i][j-1]==0:queue.appendleft([i,j-1,k])
                else: queue.append([i,j-1,k+1])
            if j<n-1 and distances[i][j]+grid[i][j+1] < distances[i][j+1]:
                distances[i][j+1] = distances[i][j] + grid[i][j+1]
                if grid[i][j+1]==0:queue.appendleft([i,j+1,k])
                else: queue.append([i,j+1,k+1])

Explain

本题解采用了广度优先搜索（BFS）的策略来找到从起点到终点移除最少障碍物的路径。为了实现这一点，代码使用了双端队列（deque）来处理两种情况：移动到空单元格和移动到障碍物单元格。如果是空单元格，则优先处理（加入队列前端），如果是障碍物，则稍后处理（加入队列尾部）。这样做的目的是尽可能地避免移除障碍物。同时，使用了一个二维数组 `distances` 来记录到每个位置的最小障碍物移除数，这有助于避免不必要的重复访问和更新。当达到终点时，即可返回当前位置的障碍物移除数。

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

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

from collections import deque
class Solution:
    def minimumObstacles(self, grid) -> int:
        m = len(grid)
        n = len(grid[0])
        queue = deque()
        queue.append([0,0,0])
        distances = [[900000 for _ in range(n)] for _ in range(m)]
        distances[0][0] = 0
        while len(queue)!=0:
            i,j,k = queue.popleft()
            if i==m-1 and j==n-1:
                return k
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < m and 0 <= y < n and distances[i][j] + grid[x][y] < distances[x][y]:
                    distances[x][y] = distances[i][j] + grid[x][y]
                    if grid[x][y] == 0:
                        queue.appendleft([x, y, k])
                    else:
                        queue.append([x, y, k+1])

Explore

在广度优先搜索（BFS）中使用双端队列（deque）可以有效地支持在队列的前端和后端快速添加和移除元素。这种灵活性相比于普通队列（通常只支持在尾部添加元素和在头部移除元素）更适合某些场景。在本题中，使用deque可以根据当前元素的类型（是否为障碍物）来决定是将新的元素加到队列的前端还是后端，这种策略可以优化搜索过程，使得路径中遇到障碍物较少的路线被优先考虑，从而更快找到最优解。

在处理到达每个单元格时，将非障碍物单元格加入队列前端，障碍物单元格加入队列尾部的区分方法，能够确保路径中较少障碍物的路线被优先处理。这种策略类似于'0-1 BFS'，用于处理图中边权重为0或1的最短路径问题。通过这种方式，算法优先探索不需要移除障碍物的路径，从而减少总的移除次数，提升算法效率，尤其是在大型网格中寻找最短路径时更为明显。

在本题中，二维数组 `distances` 用于存储到达每个单元格时所需移除的最小障碍物数量。初始化为一个非常大的数（如900000）是为了确保在初次访问任何单元格时，可以通过比较发现更小的障碍物移除数，并更新该位置。这个数值只需要大于任何可能的障碍物移除次数，通常选取一个大于网格大小乘最大障碍物数的安全值，以避免在比较时发生错误的未更新情况。

如果某个位置 `(x, y)` 的 `distances[x][y]` 已经是到达该位置时的最小障碍物移除数，理论上不应再有更小的值来更新它，因为每次访问时都是基于当前最优路径的结果。但在实际BFS过程中，可能会多次访问同一位置，特别是当路径中有回环时。这种重复访问确实会影响算法的效率，因为它增加了队列操作和不必要的计算。因此，确保每次只有当找到更优的路径时才更新`distances`并重新加入队列，是避免无效计算并提升算法效率的关键。