涉及知识点
二分查找 并集查找或BFS。
题目
在一个 n x n 的整数矩阵 grid 中,每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。
当开始下雨时,在时间为 t 时,水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的。当然,在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0,0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。
示例 1:
输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时,你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向,因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时,你才可以游向平台 (1, 1). 因为此时的水位是 3,坐标方格中的平台没有比水位 3 更高的,所以你可以游向坐标方格中的任意位置
示例 2:
输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16,此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
参数范围
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
grid[i][j] 中每个值 均无重复
分析
时间复杂度
O(log(nn)nn)。二分查找时间复杂度O(log(nn)),Can函数时间复杂度约O(n*n)。
Can函数
t时刻,起点和终点是否能连通。相邻的两个单格grid[r][c]和grid[r1][c1]如果都小于等于t,则连通。用并集查找或BFS判断起点和终点是否连通。只需要判断向右和向下的路径,向左和向上的路径必定有对应的向右或向下的路径。
二分
如果t时刻,符合要求;则t+1一定符合。对应符合要求的t,我们要找到最小值。故用左开右闭空间,t的取值范围[0,nn-1],左开右闭就是(-1,nn-1]
易错点
for (int r = 0; r < m_c; r++)
r < m_c 不能写成r+1<m_c,最后一行不能下移,可以右移。
计算掩码封装成函数,减少错误。
代码
核心代码
class CUnionFind { public: CUnionFind(int iSize) :m_vNodeToRegion(iSize) { for (int i = 0; i < iSize; i++) { m_vNodeToRegion[i] = i; } m_iConnetRegionCount = iSize; } int GetConnectRegionIndex(int iNode) { int& iConnectNO = m_vNodeToRegion[iNode]; if (iNode == iConnectNO) { return iNode; } return iConnectNO = GetConnectRegionIndex(iConnectNO); } void Union(int iNode1, int iNode2) { const int iConnectNO1 = GetConnectRegionIndex(iNode1); const int iConnectNO2 = GetConnectRegionIndex(iNode2); if (iConnectNO1 == iConnectNO2) { return; } m_iConnetRegionCount–; if (iConnectNO1 > iConnectNO2) { UnionConnect(iConnectNO1, iConnectNO2); } else { UnionConnect(iConnectNO2, iConnectNO1); } } bool IsConnect(int iNode1, int iNode2) { return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2); } int GetConnetRegionCount()const { return m_iConnetRegionCount; } vector GetNodeCountOfRegion()//各联通区域的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector> GetNodeOfRegion() { std::unordered_map<int, vector> ret; const int iNodeSize = m_vNodeToRegion.size(); for (int i = 0; i < iNodeSize; i++) { ret[GetConnectRegionIndex(i)].emplace_back(i); } return ret; } private: void UnionConnect(int iFrom, int iTo) { m_vNodeToRegion[iFrom] = iTo; } vector m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引,为了增加可理解性,用最小索引 int m_iConnetRegionCount; }; class Solution { public: int swimInWater(vector<vector>& grid) { m_c = grid.size(); int left = -1, right = m_c * m_c - 1; while (right - left > 1) { const int mid = left + (right - left) / 2; if (Can(grid, mid)) { right = mid; } else { left = mid; } } return right; } bool Can(const vector<vector>& grid, int t) { CUnionFind uf(m_c * m_c); for (int r = 0; r < m_c; r++) { for (int c = 0; c < m_c; c++) { if (grid[r][c] > t) { continue; } if ((c+1<m_c)&&(grid[r][c + 1] <= t)) { uf.Union(Mask(r,c), Mask(r, c+1)); } if ((r + 1 < m_c) && (grid[r +1 ][c] <= t)) { uf.Union(Mask(r, c), Mask(r + 1, c )); } } } return uf.IsConnect(0, m_c * m_c - 1); } int Mask(int r, int c) { return m_c * r + c; } int m_c; };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector> grid; int res = 0; { Solution slu; grid = { {0,1,2,3,4},{24,23,22,21,5},{12,13,14,15,16},{11,17,18,19,20},{10,9,8,7,6} }; res = slu.swimInWater(grid); Assert(16, res); } { Solution slu; grid = { {0,2},{1,3} }; res = slu.swimInWater(grid); Assert(3, res); }
//CConsole::Out(res); }
2023年3月旧代码
class Solution { public: int swimInWater(vector<vector>& grid) { m_r = grid.size(); m_c = grid[0].size(); int left = -1, right = 50 * 50 - 1; while (right > left + 1) { const int iMid = left + (right - left) / 2; if (CanVisit(grid, iMid)) { right = iMid; } else { left = iMid; } } return right; } bool CanVisit(const vector<vector>& vWater,int t) { vector<vector> vHasDo(m_r, vector(m_c)); std::queue<std::pair<int, int>> queRowCol; Move(0, 0, vHasDo, queRowCol,vWater,t); while (queRowCol.size()) { const int r = queRowCol.front().first; const int c = queRowCol.front().second; queRowCol.pop(); if ((r + 1 == m_r) && (c + 1 == m_c)) { return true; } Move(r+1, c, vHasDo, queRowCol, vWater,t); Move(r-1, c, vHasDo, queRowCol, vWater,t); Move(r, c+1, vHasDo, queRowCol, vWater,t); Move(r, c-1, vHasDo, queRowCol, vWater,t); } return false; } void Move(int r, int c, vector<vector>& vHasDo, std::queue<std::pair<int, int>>& queRowCol, const vector<vector>& vWater,int t ) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (vWater[r][c] >t ) { return; } if (vHasDo[r][c]) { return; } vHasDo[r][c] = true; queRowCol.emplace(r, c); } 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17