网站营销工作流程,wordpress退出登录,建设网站有什么好处,网站站内优化题目描述 这是 LeetCode 上的 「2258. 逃离火灾」 #xff0c;难度为 「困难」。 Tag : 「多源 BFS」、「二分」、「预处理」 给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid#xff0c;它表示一个网格图。 每个格子为下面 个值之一#xff1a; 0 表示草地。 1 表… 题目描述 这是 LeetCode 上的 「2258. 逃离火灾」 难度为 「困难」。 Tag : 「多源 BFS」、「二分」、「预处理」 给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid它表示一个网格图。 每个格子为下面 个值之一 0 表示草地。 1 表示着火的格子。 2 表示一座墙你跟火都不能通过这个格子。 一开始你在最左上角的格子 你想要到达最右下角的安全屋格子 。 每一分钟你可以移动到相邻的草地格子。 每次你移动之后 着火的格子会扩散到所有不是墙的相邻格子。 请你返回你在初始位置可以停留的最多分钟数且停留完这段时间后你还能安全到达安全屋。 如果无法实现请你返回 。如果不管你在初始位置停留多久你总是能到达安全屋请你返回 。 注意如果你到达安全屋后火马上到了安全屋这视为你能够安全到达安全屋。 如果两个格子有共同边那么它们为相邻格子。 示例 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 。 提示 grid[i][j] 是 0 1 或者 2。 二分 BFS 火势蔓延是一个固定的过程只有人员移动需要决策。 假设人员最晚在 秒后出发仍能到达安全屋说明人员对逃走路线的访问要比火势更快。那么人员在更早的时间点 秒后出发必然仍能按照原定路线到达安全屋火势对路径的影响不变。 因此在以 为分割点的正整数数轴上具有二段性可运用「二分」求分割点。 假设存在某个判定函数 check用于检查人员在 秒后出发能否到达安全屋那么可知 当实际延迟出发的秒数小于等于 秒必然能安全到达 当实际延迟出发的描述超过 秒必然不能安全到达 在人员移动路线中“回头路”是没有意义的因此人员对每个点的访问次数最多为一次。同时不考虑墙的阻拦火势也最多在不超过棋盘大小的时间内完全蔓延。 这指导我们最大延迟出发时间不会超过 可在 值域内进行二分。 接下来考虑如何实现 check 函数函数入参为延迟出发秒数 返回值为延迟出发后能否到达安全屋。 首先对于普通位置如果火势和人员同时到达是不允许的而安全屋 位置的同时到达是允许的。 因此我们需要使用两个二维数组 fg 和 pg 分别记录「火势」和「人员」到达某个位置的最早时间。 创建用于模拟火势蔓延的队列 fire遍历网格将火源位置进行入队更新火源位置 表示火势在第一秒时最早出现在此处 运用 BFS模拟 秒的火势蔓延火势在这 秒内所蔓延到的新位置均看作为起始火源即有 。 若执行完 秒后火势已蔓延到人员起始位置 那么延迟 秒出发不可行直接返回 False 创建用于模拟人员移动的队列 people将起始位置 进行入队更新 。 运用 BFS按照「先火后人」的方式同步模拟「火势蔓延」和「人员移动」过程。普通位置只要火势蔓延到那么人将无法移动到此处安全屋位置需要判断是否与火势同一时刻到达。 为了方便将「火势蔓延」和「人员移动」统一成 update 操作入参包括当前队列 d标识位 isFire以及移动偏移量 offset。 在进行 秒的火势蔓延时调用 次的 update(fire, true, 0)。在火势和人员同步模拟时分别调用 update(fire, true, 1) 和 update(people, false, 1)。 使用示例 来举个 Java 代码 class Solution { int[][] dirs new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}}; int n, m; boolean ok; int[][] g, fg, pg; public int maximumMinutes(int[][] grid) { g grid; n g.length; m g[0].length; fg new int[n][m]; pg new int[n][m]; if (!check(0)) return -1; int l 0, r n * m; while (l r) { int mid l r 1 1; if (check(mid)) l mid; else r mid - 1; } return r m * n ? (int)1e9 : r; } boolean check(int t) { ok false; Dequeint[] frie new ArrayDeque(); for (int i 0; i n; i) { for (int j 0; j m; j) { fg[i][j] pg[i][j] 0; if (g[i][j] 1) { fg[i][j] 1; frie.addLast(new int[]{i, j}); } } } while(t-- 0) update(frie, true, 0); // 先执行 t 秒的火势蔓延 if (fg[0][0] ! 0) return false; Dequeint[] people new ArrayDeque(); pg[0][0] 1; people.addLast(new int[]{0, 0}); while (!people.isEmpty()) { // 先火后人, 同步进行 update(frie, true, 1); update(people, false, 1); if (ok) return true; } return false; } void update(Dequeint[] deque, boolean isFrie, int offset) { int sz deque.size(); while (sz-- 0) { int[] info deque.pollFirst(); int x info[0], y info[1]; for (int[] dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (isFrie) { if (fg[nx][ny] ! 0) continue; fg[nx][ny] fg[x][y] offset; } else { if (nx n - 1 ny m - 1 (fg[nx][ny] 0 || fg[nx][ny] pg[x][y] offset)) ok true; // 火尚未到达 或 同时到达 if (fg[nx][ny] ! 0 || pg[nx][ny] ! 0) continue; pg[nx][ny] pg[x][y] offset; } deque.addLast(new int[]{nx, ny}); } } }} C 代码 class Solution {public: vectorvectorint dirs {{0,1}, {0,-1}, {1,0}, {-1,0}}; int n, m; bool ok; vectorvectorint g, fg, pg; int maximumMinutes(vectorvectorint grid) { g grid; n g.size(); m g[0].size(); fg vectorvectorint(n, vectorint(m, 0)), pg vectorvectorint(n, vectorint(m, 0)); if (!check(0)) return -1; int l 0, r n * m; while (l r) { int mid l r 1 1; if (check(mid)) l mid; else r mid - 1; } return r n * m ? (int)1e9 : r; } bool check(int t) { ok false; dequevectorint frie; for (int i 0; i n; i) { for (int j 0; j m; j) { fg[i][j] pg[i][j] 0; if (g[i][j] 1) { fg[i][j] 1; frie.push_back({i, j}); } } } while (t-- 0) update(frie, true, 0); if (fg[0][0] ! 0) return false; dequevectorint people; pg[0][0] 1; people.push_back({0, 0}); while (!people.empty()) { update(frie, true, 1); update(people, false, 1); if (ok) return true; } return false; } void update(dequevectorint deque, bool isFrie, int offset) { int sz deque.size(); while (sz-- 0) { vectorint info deque.front(); deque.pop_front(); int x info[0], y info[1]; for (vectorint dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (isFrie) { if (fg[nx][ny] ! 0) continue; fg[nx][ny] fg[x][y] offset; } else { if (nx n - 1 ny m - 1 (fg[nx][ny] 0 || fg[nx][ny] pg[x][y] offset)) ok true; if (fg[nx][ny] ! 0 || pg[nx][ny] ! 0) continue; pg[nx][ny] pg[x][y] offset; } deque.push_back({nx, ny}); } } }}; Python 代码 from collections import dequeclass Solution: def maximumMinutes(self, grid: List[List[int]]) - int: dirs [(0,1),(0,-1),(1,0),(-1,0)] ok False g grid n, m len(g), len(g[0]) fg, pg [[0] * m for _ in range(n)], [[0] * m for _ in range(n)] def update(d, isFire, offset): nonlocal ok sz len(d) for _ in range(sz): x, y d.popleft() for di in dirs: nx, ny x di[0], y di[1] if nx 0 or nx n or ny 0 or ny m: continue if g[nx][ny] 2: continue if isFire: if fg[nx][ny] ! 0: continue fg[nx][ny] fg[x][y] offset else: if nx n - 1 and ny m - 1 and (fg[nx][ny] 0 or fg[nx][ny] pg[x][y] offset): ok True if fg[nx][ny] ! 0 or pg[nx][ny] ! 0: continue pg[nx][ny] pg[x][y] offset d.append((nx, ny)) def check(t): nonlocal ok ok False fire deque() for i in range(n): for j in range(m): fg[i][j] pg[i][j] 0 if g[i][j] 1: fg[i][j] 1 fire.append((i, j)) for _ in range(t): update(fire, True, 0) if fg[0][0] ! 0: return False people deque() pg[0][0] 1 people.append((0, 0)) while people: update(fire, True, 1) update(people, False, 1) if ok: return True return False if not check(0): return -1 l, r 0, n * m while l r: mid l r 1 1 if check(mid): l mid else: r mid - 1 return int(1e9) if r n * m else r TypeScript 代码 function maximumMinutes(grid: number[][]): number { const dirs [[0,1],[0,-1],[1,0],[-1,0]]; const g grid; const n g.length, m g[0].length; const fg Array.from({length: n}, () Array(m).fill(0)), pg Array.from({length: n}, () Array(m).fill(0)); let ok false; const update function(d: number[][], isFire: boolean, offset: number) { let sz d.length; while (sz-- 0) { const info d.shift(); const x info[0], y info[1]; for (let di of dirs) { const nx x di[0], ny y di[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (isFire) { if (fg[nx][ny] ! 0) continue; fg[nx][ny] fg[x][y] offset; } else { if (nx n - 1 ny m - 1 (fg[nx][ny] 0 || fg[nx][ny] pg[x][y] offset)) ok true; if (fg[nx][ny] ! 0 || pg[nx][ny] ! 0) continue; pg[nx][ny] pg[x][y] offset; } d.push([nx, ny]); } } } const check function(t: number): boolean { ok false const fire new Array() for (let i 0; i n; i) { for (let j 0; j m; j) { fg[i][j] pg[i][j] 0; if (g[i][j] 1) { fg[i][j] 1; fire.push([i, j]); } } } while (t-- 0) update(fire, true, 0); if (fg[0][0] ! 0) return false; const people new Array(); pg[0][0] 1; people.push([0, 0]); while (people.length ! 0) { update(fire, true, 1); update(people, false, 1); if (ok) return true; } return false; } if (!check(0)) return -1; let l 0, r n * m; while (l r) { const mid l r 1 1; if (check(mid)) l mid; else r mid - 1; } return r n * m ? 1e9 : r;}; 时间复杂度在值域 范围内进行二分二分 check 的 BFS 实现复杂度为 。整体复杂度为 空间复杂度 BFS 分类讨论 经过上述解法我们发现存在大量重复计算例如每次唯一确定的“火势蔓延”过程以及每次根据最新起始火势由延迟出发时间 所决定进行的“人员移动”过程都是不必要的可通过比较双方到达时间来求解。 具体的还是用 fg 和 pg分别预处理出「火势」和「人员」到达每个网格的最早时间。其中火势蔓延唯一确定而人员的预处理是在不考虑火势的情况下进行。 根据 和 进行分情况讨论 若 人与安全屋不连通返回 若 火与安全屋不连通同时上述条件不满足 即人与安全屋是联通 返回 若 火和人都能到达安全屋。即使不考虑人员中途被火影响人员可能无法按照最佳路线前往安全屋的情况下火也比人要更早到达安全屋返回 若 理想情况下人比火更早到达安全屋但存在「人火同时到达」、「人员中途被烧」或「通路被火拦截」等问题需要进一步分情况讨论 不难发现由于安全屋的位于 人员只能从 或 两个位置之一到达安全屋这两个属于普通位置不允许人和火同时到达因此可以将「对特殊位置安全屋」的讨论转为「对普通位置」的讨论 若 人与该位置联通且 人比火更早到达该位置返回 若 人与该位置联通且 人比火更早到达该位置返回 否则说明延迟 秒出发唯二的通路会被火提前拦截需要早一秒出发返回 ; Java 代码 class Solution { int[][] dirs new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}}; int[][] g; int n, m; public int maximumMinutes(int[][] grid) { g grid; n g.length; m g[0].length; int[][] fg new int[n][m], pg new int[n][m]; Dequeint[] fire new ArrayDeque(); for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] 1) { fg[i][j] 1; fire.addLast(new int[]{i, j}); } } } bfs(fire, fg); Dequeint[] people new ArrayDeque(); people.addLast(new int[]{0, 0}); pg[0][0] 1; bfs(people, pg); int p pg[n - 1][m - 1], f fg[n - 1][m - 1], ans f - p; if (p 0) return -1; if (f 0) return (int)1e9; if (p f) return -1; if (pg[n - 1][m - 2] ! 0 ans pg[n - 1][m - 2] fg[n - 1][m - 2]) return ans; if (pg[n - 2][m - 1] ! 0 ans pg[n - 2][m - 1] fg[n - 2][m - 1]) return ans; return ans - 1; } void bfs(Dequeint[] d, int[][] time) { while (!d.isEmpty()) { int[] info d.pollFirst(); int x info[0], y info[1]; for (int[] dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (time[nx][ny] ! 0) continue; time[nx][ny] time[x][y] 1; d.addLast(new int[]{nx, ny}); } } }} C 代码 class Solution {public: vectorvectorint dirs {{0,1}, {0,-1}, {1,0}, {-1,0}}; vectorvectorint g; int n, m; int maximumMinutes(vectorvectorint grid) { g grid; n g.size(); m g[0].size(); vectorvectorint fg vectorvectorint(n, vectorint(m, 0)), pg vectorvectorint(n, vectorint(m, 0)); dequepairint, int fire; for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] 1) { fg[i][j] 1; fire.push_back({i, j}); } } } bfs(fire, fg); dequepairint, int people; people.push_back({0, 0}); pg[0][0] 1; bfs(people, pg); int p pg[n - 1][m - 1], f fg[n - 1][m - 1], ans f - p; if (p 0) return -1; if (f 0) return (int)1e9; if (p f) return -1; if (pg[n - 1][m - 2] ! 0 ans pg[n - 1][m - 2] fg[n - 1][m - 2]) return ans; if (pg[n - 2][m - 1] ! 0 ans pg[n - 2][m - 1] fg[n - 2][m - 1]) return ans; return ans - 1; } void bfs(dequepairint, int d, vectorvectorint time) { while (!d.empty()) { pairint, int info d.front(); d.pop_front(); int x info.first, y info.second; for (vectorint dir : dirs) { int nx x dir[0], ny y dir[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (time[nx][ny] ! 0) continue; time[nx][ny] time[x][y] 1; d.push_back({nx, ny}); } } }}; Python 代码 from collections import dequeclass Solution: def maximumMinutes(self, grid: List[List[int]]) - int: g grid n, m len(g), len(g[0]) dirs [(0, 1), (0, -1), (1, 0), (-1, 0)] def bfs(d, tn): while d: info d.popleft() x, y info[0], info[1] for dx, dy in dirs: nx, ny x dx, y dy if nx 0 or nx n or ny 0 or ny m: continue if g[nx][ny] 2: continue if tn[nx][ny]: continue tn[nx][ny] tn[x][y] 1 d.append((nx, ny)) fg, pg [[0] * m for _ in range(n)], [[0] * m for _ in range(n)] fire deque() for i in range(n): for j in range(m): if g[i][j] 1: fg[i][j] 1 fire.append((i, j)) bfs(fire, fg) people deque() people.append((0, 0)) pg[0][0] 1 bfs(people, pg) p, f pg[-1][-1], fg[-1][-1] ans f - p if p 0: return -1 if f 0: return int(1e9) if p f: return -1 if pg[-1][-2] ! 0 and ans pg[-1][-2] fg[-1][-2]: return ans if pg[-2][-1] ! 0 and ans pg[-2][-1] fg[-2][-1]: return ans return ans - 1 TypeScript 代码 function maximumMinutes(grid: number[][]): number { const g grid; const n g.length, m g[0].length; const dirs [[0, 1], [0, -1], [1, 0], [-1, 0]]; const bfs function (d: number[][], time: number[][]): void { while (d.length 0) { const info d.shift() as number[]; const x info[0], y info[1]; for (const dir of dirs) { const nx x dir[0], ny y dir[1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] 2) continue; if (time[nx][ny] ! 0) continue; time[nx][ny] time[x][y] 1; d.push([nx, ny]); } } } const fg Array.from({ length: n }, () Array(m).fill(0)); const pg Array.from({ length: n }, () Array(m).fill(0)); const fire []; for (let i 0; i n; i) { for (let j 0; j m; j) { if (g[i][j] 1) { fg[i][j] 1; fire.push([i, j]); } } } bfs(fire, fg); const people []; people.push([0, 0]); pg[0][0] 1; bfs(people, pg); const p pg[n - 1][m - 1], f fg[n - 1][m - 1], ans f - p; if (p 0) return -1; if (f 0) return 1e9; if (p f) return -1; if (pg[n - 1][m - 2] ! 0 ans pg[n - 1][m - 2] fg[n - 1][m - 2]) return ans; if (pg[n - 2][m - 1] ! 0 ans pg[n - 2][m - 1] fg[n - 2][m - 1]) return ans; return ans - 1;}; 时间复杂度 空间复杂度 最后 这是我们「刷穿 LeetCode」系列文章的第 No.2258 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 本文由 mdnice 多平台发布
