作者推荐
本文涉及的基础知识点
动态规划
二分查找
题目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0 表示草地。
1 表示着火的格子。
2 表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
示例 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
分析
动态规划
时间复杂度: O(n)。BFS时间复杂度O(n)，计算最晚时间O(1)。
我么把每个单格看成一个图论的一个节点，那么二维动态规划就变成了一维动态规划。我们通过广度优先可以计算出人和火到达各点时间，如果无法到达，记做109的时间达到，单格数不超过104，所以不可能这么晚到达的。
原理
| 安全屋 | 人必须比火早到或同时到达 |
| 非安全屋 | 人必须比火早到 |
令安全屋上面或左面的格子为终点。能从通过某个终点到达安全屋的充分必要条件是：
一，比火早到终点。
二，人到达终点时，火没到安全屋。
只需要考虑终点格子，不需要考虑中间格子。如果中间某个格子火追上人，则终点格子火一定能追上人。火跟着人走。
大致模块和步骤
一，封装单源BFS和多源BFS。
二，初始邻接表和初始着火点。
三，计算人和火到达各点时间。
四，计算最晚出发时间。
特殊情况分析
| 人无法到达终点 | fireEnd<=peoEnd,过 fireEnd-peoEnd-1 为负数 peoStart为负数 | |
| 人能到达终点 | 火无法到达终点、完全屋 | fireEnd为10^9 peoEnd小于mn 故 fireEnd-peoEnd-1 远大于mn |
| 人能到达终点 | 火无法到达终点、能到完全屋 | 结果正确 计算的结果是：比火到安全屋提前一天到终点，实际结果也是。 |
代码
核心代码
class Solution { public: int maximumMinutes(vector<vector<int>>& grid) { m_r = grid.size(); m_c = grid.front().size(); vector<vector<int>> vNeiB(m_r*m_c); auto Add =[&](const auto & n1, const auto & n2) { vNeiB[n1].emplace_back(n2); vNeiB[n2].emplace_back(n1); }; vector<int> vFire; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { if (2 == grid[r][c]) { continue; } const int mask = m_c * r + c; if (1 == grid[r][c]) { vFire.emplace_back(mask); } if (r && (2 != grid[r-1][c])) { Add(mask, mask - m_c); } if( c && ( 2 != grid[r][c-1])) { Add(mask, mask - 1); } } } CBFSDis disPeo(vNeiB, vector<int>{0}); CBFSDis disFire(vNeiB, vFire); const int fireEnd1 = min(disFire.m_vDis[m_r * m_c - 1 - m_c], disFire.m_vDis.back()); const int fireEnd2 = min(disFire.m_vDis[m_r * m_c - 1 - 1], disFire.m_vDis.back()); const int peoStart1 = fireEnd1 - disPeo.m_vDis[m_r * m_c - 1 - m_c] - 1; const int peoStart2 = fireEnd2 - disPeo.m_vDis[m_r * m_c - 1 - 1] - 1; const int iRet = max(peoStart1, peoStart2); if (iRet < 0) { return -1; } if (iRet > m_r * m_c) { return 1e9; } return iRet; } int m_r,m_c; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<vector<int>> grid; long long budget; { Solution slu; 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} }; auto res = slu.maximumMinutes(grid); Assert(3, res); } { Solution slu; grid = { {0,0,0,0},{0,1,2,0},{0,2,0,0} }; auto res = slu.maximumMinutes(grid); Assert(-1, res); } { Solution slu; grid = { {0,0,0},{2,2,0},{1,2,0} }; auto res = slu.maximumMinutes(grid); Assert(1000000000, res); } { Solution slu; grid = { {0,2,0,0,1},{0,2,0,2,2},{0,2,0,0,0},{0,0,2,2,0},{0,0,0,0,0} }; auto res = slu.maximumMinutes(grid); Assert(0, res); } { Solution slu; grid = { {0,0,0,0,0,0},{0,2,2,2,2,0},{0,0,0,1,2,0},{0,2,2,2,2,0},{0,0,0,0,0,0} }; auto res = slu.maximumMinutes(grid); Assert(1, res); } //CConsole::Out(res); }
2023年3月旧代码：二分查找实现
如果t1 <t2，t2能到达安全屋，则t1一定可能。我们寻找能达到的最大t，左闭右开空间。
class Solution { public: int maximumMinutes(vector<vector>& grid) { m_r = grid.size(); m_c = grid[0].size(); InitNotCanVisit(grid); if (!bfs(0, grid)) { return -1; } if (bfs(30*1000, grid)) { return 1000 * 1000 * 1000; } int left = 0, right = 30 * 1000; while (right > left + 1) { const int iMid = left + (right - left) / 2; if (bfs(iMid, grid)) { left = iMid; } else { right = iMid; } } return left; } void InitNotCanVisit(const vector<vector>& grid) { m_vNotCanVisit.assign(m_r, vector(m_c, m_iNotMay)); std::queue<std::pair<int, int>> preFire; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { if (0 != grid[r][c]) { m_vNotCanVisit[r][c] = 0; } if (1 == grid[r][c]) { preFire.emplace(r, c); } } } for (int iStep = 0; preFire.size(); iStep++) { std::queue<std::pair<int, int>> curFire; while (preFire.size()) { const int r = preFire.front().first; const int c = preFire.front().second; preFire.pop(); Fire(curFire, r + 1, c, grid,iStep); Fire(curFire, r - 1, c, grid, iStep); Fire(curFire, r, c + 1, grid, iStep); Fire(curFire, r, c - 1, grid, iStep); } preFire.swap(curFire); } m_vNotCanVisit.back().back()++; } void Fire(std::queue<std::pair<int, int>>& curFire, int r, int c, const vector<vector>& grid,const int iStep) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (m_iNotMay != m_vNotCanVisit[r][c]) { return; } m_vNotCanVisit[r][c] = iStep; curFire.emplace(r, c); } bool bfs(int iStep, const vector<vector>& grid) { std::queue<std::pair<int, int>> prePeo; vector<vector> vHasDo(m_r, vector(m_c)); prePeo.emplace(0, 0); for (; prePeo.size(); iStep++) { std::queue<std::pair<int, int>> curPeo; while (prePeo.size()) { const int r = prePeo.front().first; const int c = prePeo.front().second; if ((m_r - 1 == r) && (m_c - 1 == c)) { return true; } prePeo.pop(); MovePeo(vHasDo, curPeo, r+1, c, grid, iStep); MovePeo(vHasDo, curPeo, r - 1, c, grid, iStep); MovePeo(vHasDo, curPeo, r, c + 1, grid, iStep); MovePeo(vHasDo, curPeo, r, c - 1, grid, iStep); } prePeo.swap(curPeo); } return false; } void MovePeo(vector<vector>& vHasDo,std::queue<std::pair<int, int>>& curPeo, int r, int c, const vector<vector>& grid, const int iStep) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (iStep >= m_vNotCanVisit[r][c]) { return; } if (vHasDo[r][c]) { return; } vHasDo[r][c] = true; curPeo.emplace(r, c); } int m_r; int m_c; const int m_iNotMay = 1000 * 100; vector<vector> m_vNotCanVisit; };
2023年9月旧代码
class CBFSGridDist { public: CBFSGridDist(int r, int c) :m_r®, m_c©,m_vDis(r, vector(c, -1)), m_bCanVisit(r,vector(c,true)) { } void BFS() { while (m_que.size()) { const auto [r, c] = m_que.front(); m_que.pop(); const int iDis = m_vDis[r][c] + 1; Move(r,c,r + 1, c, iDis); Move(r, c, r - 1, c, iDis); Move(r, c, r, c + 1, iDis); Move(r, c, r, c - 1, iDis); }; } void AddDist(int r, int c, int iDis) { m_vDis[r][c] = iDis; m_que.emplace(r, c); } protected: void Move (int preR, int preC, int r, int c, int iDis) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (-1 != m_vDis[r][c]) { return; } if (!m_bCanVisit[r][c]) { return; } AddDist(r, c, iDis); }; queue<pair<int, int>> m_que; public: vector<vector> m_bCanVisit; vector<vector> m_vDis; const int m_r, m_c; }; class Solution { public: int maximumMinutes(vector<vector>& grid) { m_r = grid.size(); m_c = grid.front().size(); CBFSGridDist bfsPeo(m_r, m_c), bfsFire(m_r, m_c); for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { if (2 == grid[r][c]) { bfsFire.m_bCanVisit[r][c] = false; bfsPeo.m_bCanVisit[r][c] = false; } if (1 == grid[r][c]) { bfsFire.AddDist(r, c, 0); } } } bfsPeo.AddDist(0, 0, 0); bfsFire.BFS(); bfsPeo.BFS(); const int iPeo = bfsPeo.m_vDis.back().back(); if (-1 == iPeo) {//人无法到达 return -1; } const int iFire = bfsFire.m_vDis.back().back(); if (-1 == iFire) {//火无法到达 return 1000 * 1000 * 1000; } if (iPeo > iFire) {//火比人先到 return -1; } const int p1 = bfsPeo.m_vDis[m_r - 2].back(); const int p2 = bfsPeo.m_vDis.back()[m_c - 2]; const int f1 = bfsFire.m_vDis[m_r - 2].back(); const int f2 = bfsFire.m_vDis.back()[m_c - 2]; int iRet = -1; if ( p1 > 0) {//人通过上面进入完全屋 const int cur = min(f1<0?1e9:f1, (f2<0?1e9:f2) + 1) - (p1 + 1); iRet = max(iRet, cur); } if (p2 > 0) {//人通过左边进入安全屋 const int cur = min((f1 < 0 ? 1e9 : f1) +1, (f2 < 0 ? 1e9 : f2)) - (p2+1); iRet = max(iRet, cur); } return iRet; } int m_r, m_c; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
