【专题篇】二分

[azl397985856]

参考 2258. 逃离火灾(https://leetcode-cn.com/problems/escape-the-spreading-fire/)

[azl397985856]

思路

这个题目有明显的二段性。 即如可以停留 x 分钟， 那么我们就可以停留 y 分钟，其中 y <= x。

因此核心就是实现一个 check(t) 函数， 返回是否能停留 t 分钟。 check 函数我们可以利用 BFS 来做， 看一下停留 t 分钟能不能到达安全屋。

BFS 的基本逻辑是从 (0, 0) 点等到 t 时刻出发，然后将所有火加入队列， 用 BFS 模拟火的蔓延， 判断下能够到达 (M-1,N-1)点即可。

接下来我们套用最右二分即可。

代码

#  code from https://leetcode.com/problems/escape-the-spreading-fire/discuss/1995289/Python-BFS-Solution
# 这里的 die 函数就是上面我说的 check 函数
# 这里有一个优化点是将某个点在某个时刻是否着火的状态存了起来， 这里用 A 数组存的。
# seen[x][y] 表示 (x,y) 第一次到达的时间，初始化一个很大的数字表示还没到达
class Solution(object):
   def maximumMinutes(self, A):
       m, n = len(A), len(A[0])
       inf = 10 ** 10
       d = [[0,1],[1,0],[0,-1],[-1,0]]
       fires = [[i, j, 0] for i in range(m) for j in range(n) if A[i][j] == 1]
       A = [[inf if a < 2 else -1 for a in r] for r in A]

       def bfs(queue, seen):
           for i, j, t in queue:
               if seen[i][j] < inf: continue
               seen[i][j] = t
               for di,dj in d:
                   x, y = i + di, j + dj
                   if 0 <= x < m and 0 <= y < n and seen[x][y] >= inf and t + 1 < A[x][y]:
                       queue.append([x, y, t + 1])
       
       def die(t):
           seen = [[inf + 10] * n for i in range(m)]
           bfs([[0, 0, t]], seen)
           return seen[-1][-1] > A[-1][-1]

       bfs(fires, A)
       A[-1][-1] += 1
       return bisect_left(range(10**9 + 1), True, key=die) - 1

参考

https://leetcode.com/problems/escape-the-spreading-fire/discuss/1995289/Python-BFS-Solution