说在前面
🎈每天进行一道算法题目练习，今天的题目是“逃离火灾”。
问题描述
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 10^9 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
示例 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
思路分析
信息提取
阅读完题目后，我们可以知道以下信息：
- 格子中可能有3种情况
0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。 - 起点和终点
一开始你在最左上角的格子(0, 0)，你想要到达最右下角的安全屋格子(m - 1, n - 1)。 - 火势会向四周扩散
每秒中火势都会向四周扩散一格，但墙可以阻隔火势扩散。
解题步骤
- 1、计算每一个格子火势最快蔓延到的时间
我们可以使用dfs来模拟火势向四周扩散，并记录每一个个格子火势最快蔓延到的时间。
let fireMap = new Array(grid.length); let map = new Array(grid.length); for (let i = 0; i < fireMap.length; i++) { fireMap[i] = new Array(grid[0].length).fill(Infinity); map[i] = new Array(grid[0].length).fill(Infinity); } const fire = function (x, y, step) { if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return; if (grid[x][y] == 2 || fireMap[x][y] <= step) return; fireMap[x][y] = step; for (let i = 0; i < 4; i++) { fire(x + dx[i], y + dy[i], step + 1); } }; for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { if (grid[i][j] == 1) { fire(i, j, 0); } } }
- 2、计算在初始位置可以停留的 最多 分钟数
我们可以使用dfs来搜索可以走到终点的路径，计算到达路径上格子所需步数和火势蔓延到该格子的时间只差，其中的最小值即为在初始位置可以停留的 最多 分钟数。
let res = -Infinity; let dfs = function (x, y, step, min) { if (res == Infinity) return; if (x == grid.length - 1 && y == grid[x].length - 1) { min = Math.min(min, fireMap[x][y] - step); res = Math.max(res, min); return; } if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return; if (grid[x][y] == 2 || fireMap[x][y] <= step) return; if (map[x][y] <= step) return; map[x][y] = step; for (let i = 0; i < 4; i++) { if (res == Infinity) return; dfs( x + dx[i], y + dy[i], step + 1, Math.min(min, fireMap[x][y] - step - 1) ); } }; dfs(0, 0, 0, Infinity);
AC代码
/** * @param {number[][]} grid * @return {number} */ var maximumMinutes = function (grid) { const dx = [0, 1, 0, -1], dy = [1, 0, -1, 0]; let fireMap = new Array(grid.length); let map = new Array(grid.length); for (let i = 0; i < fireMap.length; i++) { fireMap[i] = new Array(grid[0].length).fill(Infinity); map[i] = new Array(grid[0].length).fill(Infinity); } const fire = function (x, y, step) { if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return; if (grid[x][y] == 2 || fireMap[x][y] <= step) return; fireMap[x][y] = step; for (let i = 0; i < 4; i++) { fire(x + dx[i], y + dy[i], step + 1); } }; for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { if (grid[i][j] == 1) { fire(i, j, 0); } } } let res = -Infinity; let dfs = function (x, y, step, min) { if (res == Infinity) return; if (x == grid.length - 1 && y == grid[x].length - 1) { min = Math.min(min, fireMap[x][y] - step); res = Math.max(res, min); return; } if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return; if (grid[x][y] == 2 || fireMap[x][y] <= step) return; if (map[x][y] <= step) return; map[x][y] = step; for (let i = 0; i < 4; i++) { if (res == Infinity) return; dfs( x + dx[i], y + dy[i], step + 1, Math.min(min, fireMap[x][y] - step - 1) ); } }; dfs(0, 0, 0, Infinity); if (res == Infinity) return 1000000000; return res == -Infinity ? -1 : res; };
说在后面
🎉这里是JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
