算法leetcode

【搜索难题】力扣2258-逃离火灾

字数统计: 2.8k字   |   阅读时长: 12分
, ,

摘要: 搜索题，思路简单，细节复杂

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个搜索题。思路比较清晰，不过细节很复杂。需要针对人和火搜索两次。第二次既可以 BFS 也可以 DFS，不过都有一些细节。如果用 DFS，会有重复搜索的问题，需要注意剪枝；如果用 BFS，会有一些正确性证明的问题需要注意。

题目

2258. 逃离火灾

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

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

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

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

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

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

提示：

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

示例 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
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 1e9 。

题解

记 $f(i, j)$ 表示火到达点 $(i, j)$ 的时间，也就是沿着多源最短路径到达 $(i, j)$ 的时间，如果初始时就有火，则 $f(i, j) = 0$。初始值设为 $1e9$。

记 $p(i, j)$ 表示人到达点 $(i, j)$ 的时间，也就是沿着多源最短路径到达 $(i, j)$ 的时间，$p(0, 0) = 0$。记 $\Delta(i, j) = f(i, j) - p(i, j)$ 表示火和人到达 $(i, j)$ 的时间差，我们要求的答案有以下几种情况：

  • 只要存在一条从 $(0, 0)$ 到 $(n - 1, m - 1)$ 的合法路径，路径上的所有节点均满足 $\Delta(i, j) > 0$（对于终点，可以放宽为 $\Delta(i, j)\geq 0$），则可以通关，称其为通关路径。
  • 按照行动规则无法到达终点；或者有路径到达终点，但所有的可能路径上，都存在某个点 $(i, j)$ 上不满足 $\Delta(i, j) > 0$（终点为 $\Delta(i, j)\geq 0$），则不存在通关路径，返回 $-1$。
  • 如果人有到达终点的路径，但火没有到达终点的路径，则人等多长时间都可以通关，此时返回 $1e9$。

对于某条通关路径，可以等的时间为路径上 $\Delta(i, j) - 1$ 的最小值，记为 $\delta$。（对于终点，则用 $\Delta(i, j)$ 参与最小值的比较）。所有通关路径的 $\delta$ 的最大值即为答案。

算法1：BFS + DFS

首先从所有初始时就有火的位置出发，对全图走一遍 BFS，预处理得 $f(i, j)$。

然后从 $(0, 0)$ 出发，走第二遍搜索，如果一条路径一条路径地统计，需要走 DFS。$\delta$ 初始值 $2e9$，$ans$ 初始值 $-1$。当访问到 $(i, j)$ 时，更新 $p(i, j)$ 和 $\Delta(i, j)$ 然后做以下处理：

  • $(i, j)$ 不是终点，如果 $\Delta(i, j) \leq 0$，则当前路径不合法，直接回溯。否则更新 $\delta = \min(\delta, \Delta(i, j) - 1)$，然后继续往前走。
  • $(i, j)$ 是终点，如果 $\Delta(i, j) < 0$，则当前路径不合法，直接回溯。否则找到一条通关路径，更新 $\delta = \min(\delta, \Delta(i, j))$，然后更新答案 $ans = \max(ans, \delta)$。

第二轮搜索走完后，统计答案：

  • 如果 $ans = -1$，说明没有找到通关路径，返回 -1；
  • 如果 $ans > -1$，但是很大，按照本题给的数据范围，比如 $ans > 1e8$，则说明通关路径上的点火始终到不了，返回 $1e9$。
  • 其余情况，返回 $ans$。

注意在 DFS 的过程中，同一个节点可能会访问不止一次，比如下图，$(0, 2)$ 这个点可能是向右走两步到达，也可能是先向下，然后拐个弯再向上，走 14 步到达。而这两种可能的情况均不会被火烧到。

如果首先访问的事走 14 步到达 $(0, 2)$ 的路径，则后续还会访问到走 $2$ 步到达 $(0, 2)$ 的路径，$(0, 2)$ 后续的路径会重复访问。通过最优性剪枝可以在一定程度上减少这种在错误路上越走越深的情况。

1
2
3
4
5
6
7
[[0,0,0,0,0,0,0,0,0,0,0]
,[0,2,0,2,2,2,2,2,2,2,0]
,[0,2,0,0,0,2,0,0,0,2,0]
,[0,2,0,2,0,2,0,2,0,2,0]
,[0,2,0,2,0,2,0,2,0,2,0]
,[0,2,0,2,0,2,0,2,0,2,0]
,[0,0,0,2,0,0,0,2,1,2,0]]

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from queue import Queue

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        # 预处理 f
        # f[i][j] := (i, j) 有火的时间，即最短路径的距离
        f = [[int(1e9) for _ in range(m)] for _ in range(n)]
        q = Queue() # 队列中的内容：i, j
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    f[i][j] = 0
                    q.put((i, j))
        while not q.empty():
            i, j = q.get()
            t = f[i][j]
            for d in range(4):
                nxt_i = i + dx[d]
                nxt_j = j + dy[d]
                if nxt_i < 0 or nxt_i >= n or nxt_j < 0 or nxt_j >= m:
                    continue
                if grid[nxt_i][nxt_j] != 0:
                    continue
                if f[nxt_i][nxt_j] != int(1e9):
                    continue
                f[nxt_i][nxt_j] = t + 1
                q.put((nxt_i, nxt_j))

        # 一条路径一条路径考查
        ans = [-1] # ans 引用传递
        p = [[int(1e9) for _ in range(m)] for _ in range(n)]
        def dfs(i: int, j: int, delta: int) -> None:
            # delta 值传递
            Delta = f[i][j] - p[i][j]
            if (i, j) == (n - 1, m - 1):
                if Delta < 0:
                    return
                delta = min(delta, Delta)
                # 找到一条通关路径
                ans[0] = max(ans[0], delta)
                return

            if Delta <= 0:
                # 可行性剪枝
                return
            delta = min(delta, Delta - 1)
            if delta <= ans[0]:
                # 最优性剪枝
                return

            for d in range(4):
                nxt_i = i + dx[d]
                nxt_j = j + dy[d]
                if nxt_i < 0 or nxt_i >= n or nxt_j < 0 or nxt_j >= m:
                    continue
                if grid[nxt_i][nxt_j] != 0:
                    continue
                if p[i][j] + 1 > p[nxt_i][nxt_j]:
                    continue
                p[nxt_i][nxt_j] = p[i][j] + 1
                dfs(nxt_i, nxt_j, delta)

        p[0][0] = 0
        dfs(0, 0, int(2e9))

        if ans[0] > int(1e8):
            return int(1e9)
        return ans[0]

算法2：BFS + BFS

对于人来说，一条路径一条路径地考虑，思路比较容易。但是会出现重复搜索的情况。算法性能依赖于剪枝。

直接考虑人到达各个点的最短的时间 $p(i, j)$，然后根据 $p(i, j)$ 和 $f(i, j)$ 直接更新答案。这样就可以用 BFS 求 $p$，避免 DFS 的重复搜索。

预处理出 $p$ 和 $f$ 后，对于任意一点 $(i, j)$，记 $\delta = f(i, j) - p(i, j)$，仅考虑这一点的话，最多可以等 $\delta - 1$ 分钟。

假设人从 $(0, 0)$ 沿着最短路径到 $(i, j)$，如果可以证明最短路上的每一点 $(x, y)$，都有 $f(x, y) - p(x, y) \geq \delta$。那么就可以说在人走的这条最短路上，最多可以等 $\delta - 1$。

下面用反证法，考察人从 $(0, 0)$ 到 $(i, j)$ 的最短路的某一点 $(x, y)$，该点距离 $(i, j)$ 的最短路径长度为 $d$，因此有 $d = p(i, j) - p(x, y)$。

假设在该点上 $f(x, y) - p(x, y) < \delta$，那么将 $\delta = f(i, j) - p(i, j)$ 和 $d = p(i, j) - p(x, y)$ 代入得到：

但是火从 $(x, y)$ 到 $(i, j)$ 也可以走人的最短路径，长度为 $d$，而上式是大于 $d$，因此假设不成立，$f(x, y) - p(x, y) \geq \delta$。

因此在预处理完 $f$ 和 $p$ 后，可以直接根据 $p(n-1, m-1)$ 和 $f(n-1, m-1)$ 得出结果。按以下顺序判断：

  • 首先看人能不能走到终点，如果 $p(n-1, m-1)$ 为初始值 $1e9$，则人无法到达。返回 -1。
  • 然后看火能不能到达终点，如果 $f(n-1, m-1)$ 为初始值 $1e9$，则火无法到达。返回 1e9。
  • 然后看火是否比人早到终点，如果 $f(n-1, m-1) - p(n-1, m-1) < 0$，则火比人早到终点，返回-1。
  • 如果 $f(n-1, m-1) - p(n-1, m-1) > 0$ 比较复杂，只停留 $\delta - 1$ 分钟肯定是可以的，问题是由于终点上允许人和火同时出现，因此存在可以停 $\delta$ 分钟的可能。这需要借助 $(n-2, m-1)$ 和 $(n-1, m-2)$ 这两个点的情况来判断。如果这两个点有一个点的 $f - p > \delta$，那么停 $\delta$ 就是可以的，返回 $\delta$，否则返回 $\delta - 1$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from queue import Queue

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        def bfs(ps: List[Tuple[int, int]]):
            # BFS 最短路径
            f = [[int(1e9) for _ in range(m)] for _ in range(n)]
            q = Queue() # 队列中的内容：i, j
            for s in ps:
                f[s[0]][s[1]] = 0
                q.put((s[0], s[1]))
            while not q.empty():
                i, j = q.get()
                t = f[i][j]
                for d in range(4):
                    nxt_i = i + dx[d]
                    nxt_j = j + dy[d]
                    if nxt_i < 0 or nxt_i >= n or nxt_j < 0 or nxt_j >= m:
                        continue
                    if grid[nxt_i][nxt_j] != 0:
                        continue
                    if f[nxt_i][nxt_j] != int(1e9):
                        continue
                    f[nxt_i][nxt_j] = t + 1
                    q.put((nxt_i, nxt_j))
            return f

        # 预处理 f
        # f[i][j] := (i, j) 有火的时间，即最短路径的距离
        source_points = []
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    source_points.append((i, j))
        f = bfs(source_points)

        # 预处理 p
        p = bfs([(0, 0)])

        if p[n - 1][m - 1] == int(1e9):
            return -1
        if f[n - 1][m - 1] == int(1e9):
            return int(1e9)
        delta = f[n - 1][m - 1] - p [n - 1][m - 1]
        if delta < 0:
            return -1
        if f[n - 2][m - 1] - p[n - 2][m - 1] > delta or f[n - 1][m - 2] - p[n - 1][m - 2] > delta:
            return delta
        return delta - 1
Share