千问 LeetCode 2258.逃离火灾 public int maximumMinutes(int[][] grid)

这是一个典型的「多源BFS 分类讨论」问题。核心思路是先通过多源BFS计算火蔓延到每个格子的最早时间再通过BFS计算人到达每个格子的最早时间最后通过分类讨论确定最大等待时间。 解题思路1. 计算火势蔓延时间:* 使用多源BFS将所有初始着火点作为起点计算火蔓延到地图上每个可达格子的最早时间。我们用一个二维数组 fireTime 来记录这个时间。如果火无法到达某个格子其时间记为一个极大值如 INF。2. 计算人员移动时间:* 使用单源BFS从起点 (0, 0) 开始计算在不考虑火势的情况下人到达每个可达格子的最早时间。我们用 personTime 数组记录。3. 分类讨论得出答案:* 情况一人无法到达安全屋如果 personTime[m-1][n-1] 为0表示不可达则直接返回 -1。* 情况二火无法到达安全屋如果人可达但 fireTime[m-1][n-1] 为 INF说明火永远烧不到安全屋人可以无限等待返回 10^9。* 情况三人和火均可达安全屋这是最复杂的情况。我们先计算一个理论上的最大等待时间 ans fireTime[m-1][n-1] - personTime[m-1][n-1]。这个值代表人比火早到安全屋的时间差。* 如果 ans 0人理论上可以等待 ans 分钟。但需要检查在等待 ans 分钟后人是否能在中途被火烧到。由于人只能从安全屋的上方 (m-2, n-1) 或左方 (m-1, n-2) 进入我们只需要检查这两个关键位置。* 如果人在等待 ans 分钟后到达这两个关键位置的时间仍然早于火到达的时间那么 ans 就是可行的最大等待时间。* 否则说明等待 ans 分钟会导致路径被火封锁必须提前1分钟出发返回 ans - 1。 代码实现import java.util.ArrayDeque;import java.util.Deque;class Solution {// 定义四个方向的移动上、下、左、右private static final int[][] DIRS {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 定义一个足够大的数表示无穷大不可达private static final int INF (int) 1e9;public int maximumMinutes(int[][] grid) {int m grid.length;int n grid[0].length;// 1. 计算火蔓延到每个格子的最早时间int[][] fireTime new int[m][n];Deque fireQueue new ArrayDeque();// 初始化火源队列和fireTime数组for (int i 0; i personQueue new ArrayDeque();personQueue.offerLast(new int[]{0, 0});personTime[0][0] 1; // 人从(0,0)出发时间从1开始bfs(personQueue, personTime, grid, m, n);// 3. 分类讨论int pTime personTime[m - 1][n - 1]; // 人到达安全屋的时间int fTime fireTime[m - 1][n - 1]; // 火到达安全屋的时间// 情况一人无法到达安全屋if (pTime 0) {return -1;}// 情况二火无法到达安全屋if (fTime 0) {return INF;}// 情况三人和火都可以到达安全屋// 理论上的最大等待时间int ans fTime - pTime;// 如果火比人先到安全屋则无法逃脱if (ans queue, int[][] time, int[][] grid, int m, int n) {while (!queue.isEmpty()) {int[] curr queue.pollFirst();int x curr[0];int y curr[1];for (int[] dir : DIRS) {int nx x dir[0];int ny y dir[1];// 检查边界、是否是墙、是否已经访问过if (nx 0 nx 0 ny n grid[nx][ny] ! 2 time[nx][ny] 0) {time[nx][ny] time[x][y] 1;queue.offerLast(new int[]{nx, ny});}}}}}