class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
def spread(q: Deque[int]) -> Deque[int]:
nq = deque()
while q:
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and not fire[x][y] and grid[x][y] == 0:
fire[x][y] = True
nq.append((x, y))
return nq
def check(t: int) -> bool:
for i in range(m):
for j in range(n):
fire[i][j] = False
q1 = deque()
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
fire[i][j] = True
q1.append((i, j))
while t and q1:
q1 = spread(q1)
t -= 1
if fire[0][0]:
return False
q2 = deque([(0, 0)])
vis = [[False] * n for _ in range(m)]
vis[0][0] = True
while q2:
for _ in range(len(q2)):
i, j = q2.popleft()
if fire[i][j]:
continue
for a, b in pairwise(dirs):
x, y = i + a, j + b
if (
0 <= x < m
and 0 <= y < n
and not vis[x][y]
and not fire[x][y]
and grid[x][y] == 0
):
if x == m - 1 and y == n - 1:
return True
vis[x][y] = True
q2.append((x, y))
q1 = spread(q1)
return False
m, n = len(grid), len(grid[0])
l, r = -1, m * n
dirs = (-1, 0, 1, 0, -1)
fire = [[False] * n for _ in range(m)]
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return int(1e9) if l == m * n else l