网站建设推广公司范围,Wordpress crm系统,怎么做企业网站运营,沈阳市做网站电话2023-11-09每日一题
一、题目编号
2258. 逃离火灾二、题目链接
点击跳转到题目位置
三、题目描述
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid #xff0c;它表示一个网格图。每个格子为下面 3 个值之一#xff1a;
0 表示草地。1 表示着火的格子。2 表示一…2023-11-09每日一题
一、题目编号
2258. 逃离火灾二、题目链接
点击跳转到题目位置
三、题目描述
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid 它表示一个网格图。每个格子为下面 3 个值之一
0 表示草地。1 表示着火的格子。2 表示一座墙你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) 你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟你可以移动到 相邻 的草地格子。每次你移动 之后 着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数且停留完这段时间后你还能安全到达安全屋。如果无法实现请你返回 -1 。如果不管你在初始位置停留多久你 总是 能到达安全屋请你返回 109。
注意如果你到达安全屋后火马上到了安全屋这视为你能够安全到达安全屋。
如果两个格子有共同边那么它们为 相邻 格子。 提示
m grid.lengthn grid[i].length2 m, n 3004 m * n 2 * 104grid[i][j] 是 0 1 或者 2 。grid[0][0] grid[m - 1][n - 1] 0
四、解题代码
class Solution {
public:constexpr static int INF 1e9;constexpr static int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int maximumMinutes(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint fireTime(m, vectorint(n, INF));/* 通过 bfs 求出每个格子着火的时间 */bfs(grid, fireTime);/* 二分查找找到最大停留时间 */int ans -1;int low 0, high m * n;while (low high) {int mid low (high - low) / 2; if (check(fireTime, grid, mid)) {ans mid;low mid 1;} else {high mid - 1;}}return ans m * n ? 1e9 : ans;}void bfs(vectorvectorint grid, vectorvectorint fireTime) {int m grid.size();int n grid[0].size();queuepairint, int q;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {q.emplace(i, j);fireTime[i][j] 0;}}}int time 1;while (!q.empty()) {int sz q.size();for (int i 0; i sz; i) {auto [cx, cy] q.front();q.pop();for (int j 0; j 4; j) {int nx cx dirs[j][0];int ny cy dirs[j][1];if (nx 0 ny 0 nx m ny n) {if (grid[nx][ny] 2 || fireTime[nx][ny] ! INF) {continue;}q.emplace(nx, ny);fireTime[nx][ny] time;}}}time;}}bool check(vectorvectorint fireTime, vectorvectorint grid, int stayTime) {int m fireTime.size();int n fireTime[0].size();vectorvectorbool visit(m, vectorbool(n, false));queuetupleint, int, int q;q.emplace(0, 0, stayTime);visit[0][0] true;while (!q.empty()) {auto [cx, cy, time] q.front();q.pop();for (int i 0; i 4; i) {int nx cx dirs[i][0];int ny cy dirs[i][1];if (nx 0 ny 0 nx m ny n) {if (visit[nx][ny] || grid[nx][ny] 2) {continue;}/* 到达安全屋 */if (nx m - 1 ny n - 1) {return fireTime[nx][ny] time 1;}/* 火未到达当前位置 */if (fireTime[nx][ny] time 1) {q.emplace(nx, ny, time 1);visit[nx][ny] true;}}}}return false;}
};
五、解题思路
(1) 二分查找
