逃离火灾

标签: 广度优先搜索 数组 二分查找 矩阵

难度: Hard

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

  • 0 表示草地。
  • 1 表示着火的格子。
  • 2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。

请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为 相邻 格子。

示例 1：

输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出：3
解释：上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。

示例 2：

输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出：-1
解释：上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
所以返回 -1 。

示例 3：

输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
输出：1000000000
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 109 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 300
  • 4 <= m * n <= 2 * 104
  • grid[i][j] 是 0 ，1 或者 2 。
  • grid[0][0] == grid[m - 1][n - 1] == 0

Submission

运行时间: 132 ms

内存: 19.2 MB

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fire_minutes = [[inf] * n for _ in range(m)]
        ds = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append([i, j])
                    fire_minutes[i][j] = 0
        time = 0
        while q:
            time += 1
            size = len(q)
            while size:
                size -= 1
                x, y = q.popleft()
                for dx, dy in ds:
                    x1, y1 = x + dx, y + dy
                    if 0 <= x1 < m and 0 <= y1 < n and grid[x1][y1] == 0:
                        fire_minutes[x1][y1] = time
                        grid[x1][y1] = 1
                        q.append([x1, y1])
        q.append([0, 0, 0])
        visit = [[False] * n for _ in range(m)]
        visit[0][0] = True
        ans = int(1e9)
        while q:
            size = len(q)
            tmp = -1
            while size:
                size -= 1
                x, y, t = q.popleft()
                t += 1
                for dx, dy in ds:
                    x1, y1 = x + dx, y + dy
                    if 0 <= x1 < m and 0 <= y1 < n and not visit[x1][y1] \
                      and fire_minutes[x1][y1] >= t and grid[x1][y1] != 2:
                        visit[x1][y1] = True
                        if x1 == m - 1 and y1 == n - 1:
                            return min(ans, fire_minutes[x1][y1] - t)
                        if fire_minutes[x1][y1] > t:
                            tmp = max(fire_minutes[x1][y1] - t - 1, tmp)
                            fire_minutes[x1][y1] -= t
                            q.append([x1, y1, t])
            ans = min(ans, tmp)
            if ans == -1:
                return -1
        return ans

Explain

此题解采用了双重宽度优先搜索（BFS）策略，首先对火的扩散进行模拟，然后模拟人的移动，检查是否能安全到达目的地。首先初始化一个与网格大小相同的数组 fire_minutes 来记录火到达每个格子的时间。使用一个队列 q 来存放初始的火的位置，并将对应的 fire_minutes 设为 0。使用 BFS 扩散火，更新 fire_minutes 数组。完成后，使用第二个 BFS 从起点开始，模拟人的移动。比较当前位置的时间与火到达时间，以决定是否能移动到该位置。若能到达终点，则记录并尝试寻找最大停留时间。若在 BFS 过程中发现火将完全阻挡去路，则返回 -1。最终，如果总是能安全到达，返回 109。

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

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

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fire_minutes = [[inf] * n for _ in range(m)]
        ds = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append([i, j])
                    fire_minutes[i][j] = 0
        time = 0
        while q:
            time += 1
            size = len(q)
            while size:
                size -= 1
                x, y = q.popleft()
                for dx, dy in ds:
                    x1, y1 = x + dx, y + dy
                    if 0 <= x1 < m and 0 <= y1 < n and grid[x1][y1] == 0:
                        fire_minutes[x1][y1] = time
                        grid[x1][y1] = 1
                        q.append([x1, y1])
        q.append([0, 0, 0])
        visit = [[False] * n for _ in range(m)]
        visit[0][0] = True
        ans = int(1e9)
        while q:
            size = len(q)
            tmp = -1
            while size:
                size -= 1
                x, y, t = q.popleft()
                t += 1
                for dx, dy in ds:
                    x1, y1 = x + dx, y + dy
                    if 0 <= x1 < m and 0 <= y1 < n and not visit[x1][y1] and fire_minutes[x1][y1] >= t and grid[x1][y1] != 2:
                        visit[x1][y1] = True
                        if x1 == m - 1 and y1 == n - 1:
                            return min(ans, fire_minutes[x1][y1] - t)
                        if fire_minutes[x1][y1] > t:
                            tmp = max(fire_minutes[x1][y1] - t - 1, tmp)
                            fire_minutes[x1][y1] -= t
                            q.append([x1, y1, t])
            ans = min(ans, tmp)
            if ans == -1:
                return -1
        return ans

Explore

首先模拟火的扩散是为了建立一个火到达每个格子的时间表（fire_minutes数组）。这样在模拟人的移动时，可以实时地检查每个位置是否在人到达之前就被火覆盖了。如果先模拟人的移动而没有火的时间表，我们无法有效地判断在任何给定时间点某个位置是否安全，因此先确定火的动态是解决问题的关键。

“总是能安全到达”的条件意味着在模拟过程中，人能够找到至少一条路径，在该路径上，无论人选择何时离开起点，都能在火到达之前到达终点。如果存在这样的路径，那么在算法最后会检查到人在任何时刻离开起点都可以安全到达终点，这时返回值设定为109，表示安全度非常高。

火无法扩散到墙（grid值可能为2或其他非0值表示墙）或已经着火的格子（grid值为1），因为这些格子不是可燃的或已被燃烧。在建模和算法设计中，通常只考虑将火扩散到未被燃烧的可燃物（即grid值为0的草地），这样可以简化问题并符合现实世界火的行为。

使用 `visit` 数组确实可以防止重复访问同一格子，这样做能显著提高算法的效率。虽然理论上可能存在火的扩散改变后新的路径变得可行的情况，但在本题的逻辑中，一旦某格子被访问，表示人已经在火到达前到达该格子，因此后续即使有新的路径由于火的扩散被打开，也无需重新访问，因为人已经安全通过。因此，不会遗漏真正可行的路径。