1. 火会扩散，但是我们可以看作火不会扩散到已经着火的格子，这样我们就可以记录每一个为草地的格子的着火时间
2. 在代码中，因为数字 2 已经表示墙了，所以我们把当时间为 0 时着火的格子在 gird 中的值设为 3，时间为 1 时着火的格子在 gird 中的值设为 4，以此类推，知道标注完所有可以着火的格子，通过BFS的方式就可以完成这一步
3. 通过 dfs(i, j, time) 的寻路方式来寻找可行的路径当 grid[i][j] <= time + 3 时说明 time 时刻 grid[i][j] 会着火，因此不能进行移动，除非它是终点

class Solution:def maximumMinutes(self, grid: List[List[int]]) -> int:fire = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1:fire.append([i, j])grid[i][j] = 3t = 4while len(fire) > 0:for _ in range(len(fire)):f = fire.pop(0)if f[0] + 1 < m and grid[f[0] + 1][f[1]] == 0:fire.append([f[0] + 1, f[1]])grid[f[0] + 1][f[1]] = tif f[0] - 1 >= 0 and grid[f[0] - 1][f[1]] == 0:fire.append([f[0] - 1, f[1]])grid[f[0] - 1][f[1]] = tif f[1] + 1 < n and grid[f[0]][f[1] + 1] == 0:fire.append([f[0], f[1] + 1])grid[f[0]][f[1] + 1] = tif f[1] - 1 >= 0 and grid[f[0]][f[1] - 1] == 0:fire.append([f[0], f[1] - 1])grid[f[0]][f[1] - 1] = tt += 1vis = [[0] * n for _ in range(m)]@cachedef find(i, j, time):if grid[i][j] == 2 or (grid[i][j] != 0 and grid[i][j] <= time + 3):if i == m - 1 and j == n - 1 and grid[i][j] == time + 3:return True return Falseif i == m - 1 and j == n - 1:return Truevis[i][j] = 1if i + 1 < m and vis[i + 1][j] == 0 and find(i + 1, j, time + 1)\or i > 0 and vis[i - 1][j] == 0 and find(i - 1, j, time + 1)\or j + 1 < n and vis[i][j + 1] == 0 and find(i, j + 1, time + 1)\or j > 0 and vis[i][j - 1] == 0 and find(i, j - 1, time + 1):return Truevis[i][j] = 0return Falseif find(0, 0, t):return 10**9vis = [[0] * n for _ in range(m)]if find(0, 0, 0) is False:return -1l, r = 0, t - 3while l < r - 1:mid = (l + r) >> 1vis = [[0] * n for _ in range(m)]if find(0, 0, mid):l = midelse:r = midreturn l