题解-逃离火灾-两遍BFS

Problem: 2258. 逃离火灾

• 思路
• 细节
• 解题方法
• Code

思路

• 由题意可知需要计算一条最短路,耗时最短以保证后续火传过来的时候让火传递的时间足够长来接近答案
• 火的蔓延时间用DFS求解,可以求出来火到各个节点的最少用时
• 应该考虑每次刷新一下出发时间来看此次最短路是否被烧掉吗?其实不用
  • 只需要考虑在终点人能否比火早到即可
  • 假如人在路上遇到火,则火到终点的用时一定小于等于人
• 保证了到终点的时候火耗时大于人可以反推出
  1. 人和火相遇的路都能保证有如此长的等待时间
  2. 若人和火不相遇则显然

细节

1. 如果起点起火不可达
2. 对于只有人可达的情况,是等待多久都可以的情况
3. 重点:因为允许人和火同时进安全屋,但是不能要求其他格子里人和火同时到
   1. 考虑将终点旁边的两格当做终点,如果他们到达终点所剩下的时间大于等于1,显然可以在外面等一分钟

解题方法

• 两遍BFS求火和人到各个节点的距离
• 对于起点和终点的几种情况特判
• 查询以终点左边和上边的点是否允许多等一分钟
• 返回答案

Code

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        n=len(grid[0])
        m=len(grid)
        times=[[0x7fffffff]*n for _ in range(m)]
        q=deque()
        directions=[[0,-1],[0,1],[1,0],[-1,0]]
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    q.append([i,j])
                elif grid[i][j]==2:
                    times[i][j]=-1#不可达
        now=0
        h=set()  
        while q:
            length=len(q)
            for _ in range(length):
                i,j=q.popleft()
                times[i][j]=now
                h.add((i,j))
                for dx,dy in directions:
                    x,y=i+dx,j+dy
                    if 0<=x<m and 0<=y<n and grid[x][y]!=2 and (x,y) not in h:
                        q.append((x,y)) 
            now+=1
        #然后我们求人到各个节点用时
        people=[[0x7fffffff]*n for _ in range(m)]
        q.append((0,0))
        h.clear()
        now=0
        h=set()  
        while q:
            length=len(q)
            for _ in range(length):
                i,j=q.popleft()
                people[i][j]=now
                h.add((i,j))
                for dx,dy in directions:
                    x,y=i+dx,j+dy
                    if 0<=x<m and 0<=y<n and grid[x][y]!=2 and grid[x][y]!=1 and (x,y) not in h:
                        q.append((x,y)) 
            now+=1
        if times[-1][-1]<people[-1][-1] or people[-1][-1]==0x7fffffff:
            return -1 
        if times[0][0]==0:
            return -1
        if times[-1][-1]==0x7fffffff:
            return 1000000000#火不可达,说明人到火这一路都没有火
        maxNeed=times[-1][-1]-people[-1][-1]
        if times[-1][-2]>people[-1][-2]+maxNeed or times[-2][-1]>people[-2][-1]+maxNeed:
            return maxNeed
        return maxNeed-1