题目
给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。
一开始在第 0 天，整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成 水域 （也就是 0 变成 1 ）。
你想知道从矩阵最 上面 一行走到最 下面 一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发，到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动（也就是上下左右）。
请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。
示例 1：
输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。
示例 2：
输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。
示例 3：
输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。
参数范围：
2 <= row, col <= 2 * 104
4 <= row * col <= 2 * 104
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
cells 中的所有格子坐标都是 唯一 的。
二分查找分析
时间复杂度
O(nlogn) ，二分查找O(logn)，并集查找O(n)。
分析
随着天数的增大，逐步从能过变成不能过。左闭右开空间。
并集查找的时候只需要连接左边和上边。第一行下移，就是第二行上移。
代码
核心代码
class Solution { public: int latestDayToCross(int row, int col, vector& cells) { m_r = row; m_c = col; int left = 0, right = m_r * m_c ; while (right - left > 1) { const auto mid = left + (right - left) / 2; vector mat(row, vector(col)); for (int i = 0; i < mid; i++) { mat[cells[i][0]-1][cells[i][1]-1] = 1; } if (Can(mat)) { left = mid; } else { right = mid; } } return left; } bool Can(const vector& mat) { const int n = m_r*m_c; CUnionFind uf(n + 2); for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { if (1 == mat[r][c]) { continue; } if ((0 != r) && (0 == mat[r - 1][c])) { uf.Union(r * m_c + c, (r - 1) * m_c + c); } if ((0 != c) && (0 == mat[r][c - 1])) { uf.Union(r * m_c + c, r * m_c + c - 1); } } } for (int c = 0; c < m_c; c++) { if (0 == mat[0][c]) { uf.Union(n, c); } if (0 == mat[m_r - 1][c]) { uf.Union(n+1, (m_r - 1) * m_c + c); } } return uf.IsConnect(n, n + 1); } int m_r,m_c; };
测试用例
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]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { int row, col, res; vector cells; { row = 2, col = 2, cells = { {1,1},{2,1},{1,2},{2,2} }; Solution slu; auto res = slu.latestDayToCross(row, col, cells); Assert(2, res); } { row = 2, col = 2, cells = { {1,1},{1,2},{2,1},{2,2} }; Solution slu; auto res = slu.latestDayToCross(row, col, cells); Assert(1, res); } { row = 6, col = 2, cells = { {4, 2}, { 6,2 }, { 2,1 }, { 4,1 }, { 6,1 }, { 3,1 }, { 2,2 }, { 3,2 }, { 1,1 }, { 5,1 }, { 5,2 }, { 1,2 } }; Solution slu; auto res = slu.latestDayToCross(row, col, cells); Assert(3, res); }
//CConsole::Out(res);
}
逆序思考
反向思考：水慢慢变成陆地，最晚什么时候连通陆地。
时间复杂度😮(n)
代码
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<int> GetNodeCountOfRegion()//各联通区域的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector<int> vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector<int>> GetNodeOfRegion() { std::unordered_map<int, vector<int>> 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<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引 int m_iConnetRegionCount; }; class Solution { public: int latestDayToCross(int row, int col, vector<vector<int>>& cells) { m_r = row; m_c = col; const int n = m_r * m_c; CUnionFind uf(n + 2); for (int c = 0; c < m_c; c++) { uf.Union(n, c); uf.Union(n + 1, (m_r - 1) * m_c + c); } vector<vector<int>> mat(row, vector<int>(col,1)); for (int i = cells.size() - 1; i >= 0; i--) { const int r = cells[i][0] - 1; const int c = cells[i][1] - 1; mat[r][c] = 0; auto Add = [&](const int rNew, const int cNew) { if ((rNew < 0) || (rNew >= m_r)) { return; } if ((cNew < 0) || (cNew >= m_c)) { return; } if (0 == mat[rNew][cNew]) { uf.Union(r * m_c + c, rNew * m_c + cNew); } }; Add(r + 1, c); Add(r - 1, c); Add(r, c - 1); Add(r, c + 1); if (uf.IsConnect(n, n + 1)) { return i ; } } return 0; } int m_r,m_c; };
2023年3月旧代码
class Solution { public: int latestDayToCross(int row, int col, vector& cells) { m_r = row; m_c = col; int left = 0,r = cells.size()+1 ; while (r > left + 1) { int iMid = left + (r - left) / 2; vector mat(m_r, vector(m_c)); for (int i = 0; i < iMid; i++) { mat[cells[i][0]-1][cells[i][1]-1] = 1; } if (bfs(mat)) { left = iMid; } else { r = iMid; } } return left; } bool bfs(const vector& mat) { std::queue> queCanViste; std::unordered_map setDo; for (int c = 0; c < m_c; c++) { Add(queCanViste, setDo, 0, c, mat); } while (queCanViste.size()) { const int r = queCanViste.front().first; const int c = queCanViste.front().second; if (r == m_r - 1) { return true; } queCanViste.pop(); Add(queCanViste, setDo, r+1, c, mat); Add(queCanViste, setDo, r-1, c, mat); Add(queCanViste, setDo, r , c+1, mat); Add(queCanViste, setDo, r, c-1, mat); } return false; } void Add(std::queue>& queCanViste, std::unordered_map& setDo, int r, int c,const vector& mat) { if ((r < 0) || (r >= m_r)) { return; } if ((c<0) || (c >=m_c)) { return; } if (1 == mat[r][c]) { return; } if (setDo[r].count©) { return; } queCanViste.emplace(r, c); setDo[r].emplace©; } int m_r, m_c; };
2023年9月旧代码
class Solution { public: int latestDayToCross(int row, int col, vector& cells) { m_c = col; int iMaskNum = row * col; vector grid(row, vector(col)); for (auto& v : cells) { v[0]–; v[1]–; grid[v[0]][v[1]] = 1; } CUnionFind uf(iMaskNum+2);//增加两个特殊端点; iMaskNum 连接所有第0行 iMaskNum+1 连接多有最后一行 auto Add = [&row,this,&grid,&uf](int iMask, int r, int c) { if ((r < 0) || (r >= row)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (1 == grid[r][c]) { return; } uf.Union(iMask, Mask(r, c)); }; for (int r = 0; r < row; r++) { for (int c = 0; c < m_c; c++) { if (1 == grid[r][c]) { continue; } const int mask = Mask(r, c); Add(mask, r + 1, c); Add(mask, r, c + 1); } } for (int c = 0; c < m_c; c++) { uf.Union(iMaskNum, Mask(0, c)); uf.Union(iMaskNum+1, Mask(row-1, c)); } for (int i = cells.size() - 1; i >= 0; i–) { if (uf.IsConnect(iMaskNum, iMaskNum+1)) { return i+1; } const auto& v = cells[i]; grid[v[0]][v[1]] = 0; const int mask = Mask(v[0], v[1]); Add(mask, v[0] + 1, v[1]); Add(mask, v[0], v[1] + 1); Add(mask, v[0] - 1, v[1]); Add(mask, v[0], v[1] - 1); } return 0; } inline int Mask(int r, int c) { return r * m_c + c; } int 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
