title
给你一个下标从 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.lengthn == grid[i].length2 <= m, n <= 3004 <= m * n <= 2 * 104grid[i][j]是0，1或者2。grid[0][0] == grid[m - 1][n - 1] == 0
solution
use bisection metthod.
Use BFS to find the fastest path to end.
MOD = int(1e9 + 7)
INF = float('inf')
import sortedcontainers
import bisect
import heapq
class Directions:
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
diagonal_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
all_dirs = dirs + diagonal_dirs
class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ft = [[-1 for _ in range(n)] for _ in range(m)]
queue = collections.deque()
for i in range(m):
for j in range(n):
v = grid[i][j]
if v == 1:
queue.append((i, j))
ft[i][j] = 0
elif v == 2:
ft[i][j] = 0
level = 0
while queue:
level += 1
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and ft[nx][ny] == -1:
ft[nx][ny] = level
queue.append((nx, ny))
# print(ft)
def bfs(used):
if ft[0][0] != -1 and used >= ft[0][0]:
return False
if ft[m - 1][n - 1] != -1 and used >= ft[m - 1][n - 1]:
return False
q = collections.deque()
q.append((0, 0))
level = 0
visit = set()
visit.add((0, 0))
while q:
level += 1
for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if (nx, ny) in visit: continue
visit.add((nx, ny))
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
if ft[nx][ny] >= 0 and level + used >= ft[nx][ny]:
if level + used == ft[nx][ny] and (nx, ny) == (m - 1, n - 1):
return True
continue
if (nx, ny) == (m - 1, n - 1):
return True
# print(nx, ny)
q.append((nx, ny))
return False
if bfs(m * n):
return 10 ** 9
elif not bfs(0):
return -1
import bisect
r = bisect.bisect_left(range(m * n + 1), True, lo=1, hi=m * n, key=lambda p: not bfs(p))
# print(r)
return r - 1