说在前面
🎈每天进行一道算法题目练习，今天的题目是“逃离火灾”。
问题描述
给你一个下标从 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
