LeetCode 2258. 逃离火灾：BFS

编程入门行业动态更新时间:2024-10-23 11:31:51

LeetCode 2258. 逃离<a href=https://www.elefans.com/category/jswz/34/1747972.html style= 火灾：BFS"/>

LeetCode 2258. 逃离火灾：BFS

【LetMeFly】2258.逃离火灾

力扣题目链接：/

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到相邻的草地格子。每次你移动之后，着火的格子会扩散到所有不是墙的相邻格子。

请你返回你在初始位置可以停留的最多分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你总是能到达安全屋，请你返回 10⁹ 。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为相邻格子。

示例 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
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 10⁹ 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 10⁴
grid[i][j] 是 0 ，1 或者 2 。
grid[0][0] == grid[m - 1][n - 1] == 0

方法一：二分 + BFS

首先以所有的🔥为起点开始广度优先搜索，这样我们就能得到“火焰燃烧图”（🔥燃烧到某个坐标所需耗时）。

接着可以二分“👱的开局等待时长”。假设开局等待时间为 t t t，那么就从时间 t t t开始对👱能到达的位置进行广度优先搜索。

在对👱的广搜过程中：

若搜索到了“安全屋”的位置：若“👱的到达耗时小于等于🔥的到达耗时”，则表示👱能等待时间 t t t后再出发
否则（非安全屋位置）：若“👱的到达耗时小于🔥的到达耗时”，则表示人能到达该位置

以上，即可。

时间复杂度 O ( m n log ⁡ m n ) O(mn\log mn) O(mnlogmn)，其中 s i z e ( g r i d ) = m × n size(grid)=m\times n size(grid)=m×n
空间复杂度 O ( m n ) O(mn) O(mn)

AC代码

C++

class Solution {
private:int m, n;int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};vector<vector<int>> fireTime;void debug(vector<vector<int>>& v) {for (auto& t : v) {for (auto& tt : t) {cout << tt << ' ';}cout << endl;}}void bfsFire(vector<vector<int>>& grid) {  // 计算火燃烧到每个位置时所需耗时并存入fireTimevector<vector<int>> graph = grid;fireTime = vector<vector<int>>(m, vector<int>(n, 1e9));queue<pair<int, int>> q;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (graph[i][j] == 1) {q.push({i, j});fireTime[i][j] = 0;}}}while (q.size()) {auto [x, y] = q.front();q.pop();for (int d = 0; d < 4; d++) {int tx = x + direction[d][0];int ty = y + direction[d][1];if (tx >= 0 && tx < m && ty >= 0 && ty < n && !graph[tx][ty]) {graph[tx][ty] = 1;fireTime[tx][ty] = fireTime[x][y] + 1;q.push({tx, ty});}}}}bool check(vector<vector<int>>& grid, int t) {  // 其实是bfsPeoplevector<vector<int>> peopleTime(m, vector<int>(n, 0)), graph(grid);peopleTime[0][0] = t;queue<pair<int, int>> q;q.push({0, 0});graph[0][0] = 2;while (q.size()) {auto [x, y] = q.front();q.pop();for (int d = 0; d < 4; d++) {int tx = x + direction[d][0];int ty = y + direction[d][1];int toTime = peopleTime[x][y] + 1;if (tx >= 0 && tx < m && ty >= 0 && ty < n && !graph[tx][ty]) {graph[tx][ty] = 2;if (tx == m - 1 && ty == n - 1 && toTime <= fireTime[m - 1][n - 1]) {return true;}if (toTime < fireTime[tx][ty]) {peopleTime[tx][ty] = toTime;q.push({tx, ty});}}}}return false;}
public:int maximumMinutes(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();bfsFire(grid);int l = 0, r = n * m;int ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (check(grid, mid)) {ans = mid;l = mid + 1;}else {r = mid - 1;}}return ans >= n * m ? 1e9 : ans;}
};

Python

# from typing import List
# from copy import deepcopyclass Solution:def __init__(self) -> None:self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]def bfsFire(self, grid: List[List[int]]) -> None:fireTime = [[int(1e9)] * self.n for _ in range(self.m)]graph = deepcopy(grid)q = []for i in range(self.m):for j in range(self.n):if graph[i][j] == 1:q.append((i, j))fireTime[i][j] = 0while q:x, y = q[0]q = q[1:]for dx, dy in self.direction:tx, ty = x + dx, y + dyif tx >= 0 and tx < self.m and ty >= 0 and ty < self.n and not graph[tx][ty]:q.append((tx, ty))fireTime[tx][ty] = fireTime[x][y] + 1graph[tx][ty] = 1self.fireTime = fireTimedef check(self, grid: List[List[int]], t: int) -> bool:if t == 4:print(self.fireTime)peopleTime = [[0] * self.n for _ in range(self.m)]graph = deepcopy(grid)q = []q.append((0, 0))graph[0][0] = 2peopleTime[0][0] = twhile q:x, y = q[0]q = q[1:]thisTime = peopleTime[x][y] + 1for dx, dy in self.direction:tx, ty = x + dx, y + dyif tx >= 0 and tx < self.m and ty >= 0 and ty < self.n and not graph[tx][ty]:graph[tx][ty] = 2if tx == self.m - 1 and ty == self.n - 1 and thisTime <= self.fireTime[-1][-1]:return Trueif thisTime < self.fireTime[tx][ty]:peopleTime[tx][ty] = thisTimeq.append((tx, ty))return Falsedef maximumMinutes(self, grid: List[List[int]]) -> int:self.m, self.n = len(grid), len(grid[0])self.bfsFire(grid)l, r = 0, self.m * self.nans = -1while l <= r:mid = (l + r) // 2if self.check(grid, mid):ans = midl = mid + 1else:r = mid - 1return int(1e9) if ans >= self.m * self.n else ansif __name__ == '__main__':print(Solution().maximumMinutes([[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]]))"""[[6, ∞, 4, 3, 2, 1, 2],[5, 4, 3, ∞, ∞, 0, 1],[6, ∞, 2, 1, 0, ∞, 2],[7, 8, ∞, ∞, ∞, 14, ∞],[8, 9, 10, 11, 12, 13, 14]]"""