网站设计做图工具,发布 php 微网站,做网站登入见面,360做网站多少钱一年作者推荐
本文涉及的基础知识点
二分查找算法合集 动态规划 二分查找
题目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid #xff0c;它表示一个网格图。每个格子为下面 3 个值之一#xff1a; 0 表示草地。 1 表示着火的格子。 2 表示一座墙#xff0c;你跟…作者推荐
本文涉及的基础知识点
二分查找算法合集 动态规划 二分查找
题目
给你一个下标从 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。 二初始邻接表和初始着火点。 三计算人和火到达各点时间。 四计算最晚出发时间。
特殊情况分析
人无法到达终点fireEndpeoEnd,过 fireEnd-peoEnd-1 为负数 peoStart为负数人能到达终点火无法到达终点、完全屋fireEnd为10^9 peoEnd小于mn 故 fireEnd-peoEnd-1 远大于mn人能到达终点火无法到达终点、能到完全屋结果正确 计算的结果是比火到安全屋提前一天到终点实际结果也是。
代码
核心代码
class Solution {
public:int maximumMinutes(vectorvectorint grid) {m_r grid.size();m_c grid.front().size();vectorvectorint vNeiB(m_r*m_c);auto Add [](const auto n1, const auto n2){vNeiB[n1].emplace_back(n2);vNeiB[n2].emplace_back(n1);};vectorint 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, vectorint{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;
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorvectorint 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 t2t2能到达安全屋则t1一定可能。我们寻找能达到的最大t左闭右开空间。
class Solution { public: int maximumMinutes(vectorvector 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 vectorvector grid) { m_vNotCanVisit.assign(m_r, vector(m_c, m_iNotMay)); std::queuestd::pairint, 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::queuestd::pairint, 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::queuestd::pairint, int curFire, int r, int c, const vectorvector 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 vectorvector grid) { std::queuestd::pairint, int prePeo; vectorvector vHasDo(m_r, vector(m_c)); prePeo.emplace(0, 0); for (; prePeo.size(); iStep) { std::queuestd::pairint, 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, r1, 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(vectorvector vHasDo,std::queuestd::pairint, int curPeo, int r, int c, const vectorvector 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; vectorvector 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); }; queuepairint, int m_que; public: vectorvector m_bCanVisit; vectorvector m_vDis; const int m_r, m_c; };
class Solution { public: int maximumMinutes(vectorvector 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(f10?1e9:f1, (f20?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)) - (p21); iRet max(iRet, cur); } return iRet; } int m_r, m_c; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业
。也就是我们常说的专业的人做专业的事。 | |如果程序是一条龙那算法就是他的是睛|
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
