综合-BFS

lc 2023/11/09每日一题

给你一个下标从 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

解法一

常规二分+bfs模拟，不多解释，时间复杂度O(nmlog(nm))

import copy
from collections import deque
from typing import List

DIRS = [(0, 1), (0, -1), (-1, 0), (1, 0)]


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

        l, r = 0, n * m

        def check(s: int) -> bool:
            u = copy.deepcopy(grid)
            q = deque()
            for i in range(n):
                for j in range(m):
                    if u[i][j] == 1:
                        q.append((i, j))
            while s > 0:
                le = len(q)
                while le > 0:
                    poll = q.popleft()
                    x, y = poll[0], poll[1]
                    for dx, dy in DIRS:
                        xx, yy = x + dx, y + dy
                        if n > xx >= 0 and m > yy >= 0 and u[xx][yy] == 0:
                            u[xx][yy] = 1
                            q.append((xx, yy))
                    le -= 1
                s -= 1
            if u[0][0] == 1 or u[n - 1][m - 1] == 1:
                return False
            q2 = deque()
            q2.append((0, 0))
            vis = [[0] * m for _ in range(n)]
            vis[0][0] = 1
            while q2:
                sz2 = len(q)
                flag = False
                while sz2:
                    poll = q.popleft()
                    x, y = poll[0], poll[1]
                    for dx, dy in DIRS:
                        xx, yy = x + dx, y + dy
                        if n > xx >= 0 and m > yy >= 0 and u[xx][yy] == 0:
                            u[xx][yy] = 1
                            if xx == n - 1 and yy == m - 1:
                                flag = True
                            q.append((xx, yy))
                    sz2 -= 1
                sz1 = len(q2)
                while sz1:
                    poll = q2.popleft()
                    x, y = poll[0], poll[1]
                    if x == n - 1 and y == m - 1:
                        return True
                    for dx, dy in DIRS:
                        xx, yy = x + dx, y + dy
                        if n > xx >= 0 and m > yy >= 0 and (
                                u[xx][yy] == 0 or xx == n - 1 and yy == m - 1 and flag) and not vis[xx][yy]:
                            q2.append((xx, yy))
                            vis[xx][yy] = 1
                    sz1 -= 1
            return False

        while l < r:
            mid = (l + r + 1) // 2
            if check(mid):
                l = mid
            else:
                r = mid - 1
        if l == m * n:
            return 10 ** 9
        else:
            return l if check(l) else -1

解法二

O(nm)做法，单源BFS(人)+多源BFS(火)，计算出每个位置被人或者是火最早到达的时间分别为g1、g2,一个简单的设想，假设人可以到达安全位置(n - 1, m - 1)的话，那么答案为$g2[n - 1][m - 1] - g1[n - 1][m - 1]$,但是这个答案是我们理想状态下的，并且是题目恰好有一个条件就是可以在安全位置允许火和人同时到达，但在这种情况下无法保证其他的可以到达的点都是人先到然后火后到，又由于$(n - 1, m - 1)是由(n - 2, m - 1)或者(n - 1, m - 2)而转移来的，那么只需要保证在对于这两个转移点$$进行判断时,存在其一g2[x][y] - g1[x][y] > (g2[n - 1][m - 1] - g1[n - 1][m - 1])就可以保证答案为最$$理想的结果，否则则减一,减一一定可以保证人先到，火后到。$

from collections import deque
from typing import List

"""
aa/bb  aa:人 bb:火
理想情况
xx/xx 12/12
10/14 11/13

特殊情况
xx/xx 12/12
10/12 11/13
"""

DIRS = [(0, 1), (0, -1), (-1, 0), (1, 0)]


class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        g1, g2 = [[-1] * m for _ in range(n)], [[-1] * m for _ in range(n)]
        q = deque()
        g1[0][0] = 0
        q.append((0, 0, 0))
        while q:
            poll = q.popleft()
            x, y, v = poll[0], poll[1], poll[2]
            for dx, dy in DIRS:
                xx, yy = x + dx, y + dy
                if 0 <= xx < n and 0 <= yy < m and g1[xx][yy] == -1 and grid[xx][yy] == 0:
                    g1[xx][yy] = v + 1
                    q.append((xx, yy, v + 1))
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    g2[i][j] = 0
                    q.append((i, j, 0))
        while q:
            poll = q.popleft()
            x, y, v = poll[0], poll[1], poll[2]
            for dx, dy in DIRS:
                xx, yy = x + dx, y + dy
                if 0 <= xx < n and 0 <= yy < m and g2[xx][yy] == -1 and grid[xx][yy] == 0:
                    g2[xx][yy] = v + 1
                    q.append((xx, yy, v + 1))
        if g1[n - 1][m - 1] == -1 or g2[n - 1][m - 1] != -1 and g2[n - 1][m - 1] < g1[n - 1][m - 1]:
            return -1
        if g2[n - 1][m - 1] == -1:
            return 10 ** 9
        d = g2[n - 1][m - 1] - g1[n - 1][m - 1]
        if g1[n - 2][m - 1] + d < g2[n - 2][m - 1] and grid[n - 2][m - 1] != 2 or g1[n - 1][m - 2] + d < g2[n - 1][
            m - 2] and grid[n - 1][m - 2] != 2:
            return d
        return d - 1