题目给的还是比较绕的，非要说什么人可以等几分钟出发。初始状态，是 人、火源、防火墙 的位置点。每分钟发生的时候，火会往之前没有着的格子（不能是墙）烧；人可以去没有火的地方。
Bakerston 的回答非常漂亮，而且图文并茂。一起学习一下：
方法1：广度优先搜索 + 二分查找
用 BFS 来找到并更新着火的格子和安全的格子：
第一天，火从右上角，向左边和下面蔓延；人可去到下面和右边；
第二天，火接着向 左、下蔓延；第一排的人没有办法向右，只能向下；
同理来到第三天。
然后我们怎么知道我们可以到达绿色的安全格子呢？
因为每一天，火在我们移动前蔓延的，所以：
- 如果我们在火烧了绿格子的一天及之后到达，fail，失败；【题目中有说：注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。】
- 如果在同一天或提前，success，成功。
看啊，就是上面所画的。
接下来回到问题，我们看看可以停留多久：
假设我们待 x 天会失败，那我们应该待得更短： x-1 天；
假如我们待 x 天会成功，那我们应该待得更长一点： x+1 天。
这就变成了一个经典的二分搜索问题。
大佬谦虚了，说代码有点丑陋：
def maximumMinutes(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
fires, seen = [], set()
f = collections.deque()
for i in range(m):
for j in range(n):
if A[i][j] == 1: # 1 表示着火的格子
fires.append((i, j))
seen.add((i, j)) # set
f.append((i, j)) # deque
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 移动方向
# If we stay for 'days' days.
def helper(days):
fire, seen = fires[::], set()
# Let the fire spreads for 'days' days.
while days > 0:
newfire = []
for i, j in fire:
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
# If the fire reach us before we move, we fail.
if ni == 0 and nj == 0:
return False
seen.add((ni, nj))
newfire.append((ni, nj))
fire = newfire[::]
days -= 1
# Then let the fire and us move by turn (fire first).
safe = [(0, 0)]
while safe:
# Fire spreads first.
newfire = []
for i, j in fire:
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
# If the fire reaches bot-right cell, if we are just one step close to bot-right cell
# We can still reach it, otherwise we fail. (Please refer to picture 2)
if ni == m - 1 and nj == n - 1:
if not ((m - 2, n - 1) in safe or (m - 1, n - 2) in safe):
return False
seen.add((ni, nj))
newfire.append((ni, nj))
fire = newfire[::]
# We move then.
newsafe = []
for i, j in safe:
for di, dj in dirs:
ni, nj = i + di, j + dj
# If we can reach bot-right cell, success.
if ni == m - 1 and nj == n - 1:
return True
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
seen.add((ni, nj))
newsafe.append((ni, nj))
safe = newsafe[::]
# If there is no more cell for us to move before reaching bot-right cell, we fail.
return False
# check if always safe:
while f:
i, j = f.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
seen.add((ni, nj))
f.append((ni, nj))
f = collections.deque([(0, 0)])
while f:
i, j = f.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
if ni == m - 1 and nj == n - 1:
return 10 ** 9
seen.add((ni, nj))
f.append((ni, nj))
# Binary search to find maximum days:
l, r = 0, 10 ** 4
while l < r:
mid = (l + r + 1) // 2
if helper(mid):
l = mid
else:
r = mid - 1
return l if helper(l) else -1第二种方法：
Thanks to cza_wudi’s solution.
我们只需要 BFS 两遍，就可以找到人和火的最早到达右下角的时间，然后作比较就可以了。
第一排，计算人到安全区域的时间，是 9 次移动；
第二排，计算火到安全区域的最早时间，是 10 次移动。
有一种 人 和 火 赛跑的感觉有没有。
我们只能关注抵达最右下角的时间差。因为在从【左上->右下】这样方向确定的路线上，时间差是非增的。
参考下面这张图，假设我们比火领先 2 天到，就是说，火在两天后到达我们刚刚去过的地方。因为火只能延特定的路径走，所以我们在剩下的路线上都是领先 2 步的。所以我们可以用这个时间差来计算题目里说，我们可以在原地等多久。
要注意好 边缘案例：
如果我们不能抵达 安全点，返回 -1；
如果火到不了 安全点，返回 10**9；
我们提前 x 天到安全点，意味着，我们可以待 x 天，也可以待 x-1 天，取决于我们是否会被火紧跟着。如果火紧随其后，则意味着大火与人相同的道路。因此，如果时间差为 x 天，则在同一路径中，如果您延迟 x 天出发，您将在同一单元格中与大火相同，因此该人最多可以延迟（x -1）天，以确保该人至少领先一个格子。
相反，如果火势来自相反的方向，则不必担心火在相同的路径上，这意味着只有接触点，就在右下。
这种思路的代码：
def maximumMinutes(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ppl_time = [[-1] * n for _ in range(m)]
fire_time = [[-1] * n for _ in range(m)]
# BFS for people's arrival for each cell.
ppl_front = collections.deque([(0, 0, 0)])
while ppl_front:
cx, cy, days = ppl_front.popleft()
ppl_time[cx][cy] = days
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 0 and ppl_time[nx][ny] == -1:
ppl_front.append((nx, ny, days + 1))
# BFS for fire's arrival for each cell.
fire_front = collections.deque([(x, y, 0) for x in range(m) for y in range(n) if A[x][y] == 1])
while fire_front:
cx, cy, days = fire_front.popleft()
fire_time[cx][cy] = days
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 0 and fire_time[nx][ny] == -1:
fire_front.append((nx, ny, days + 1))
# Check the arrival days for the bottom-right cell.
ppl_arrival = ppl_time[-1][-1]
fire_arrival = fire_time[-1][-1]
# Some edge cases.
if ppl_arrival == -1:
return -1
if fire_arrival == -1:
return 10 ** 9
if fire_arrival < ppl_arrival:
return -1
# Whether we are 'followed' by fire on both two pathes toward bot-right cell.
diff = fire_arrival - ppl_arrival
ppl_1, ppl_2 = ppl_time[-1][-2], ppl_time[-2][-1]
fire_1, fire_2 = fire_time[-1][-2], fire_time[-2][-1]
if ppl_1 > -1 and ppl_2 > -1 and (fire_1 - ppl_1 > diff or fire_2 - ppl_2 > diff):
return diff
return diff - 1