本文涉及的基础知识点
作者推荐
题目
给你一个下标从 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<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<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<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<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<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<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<vector>& mat) { std::queue<std::pair<int, int>> queCanViste; std::unordered_map<int, std::unordered_set> 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<std::pair<int, int>>& queCanViste, std::unordered_map<int, std::unordered_set>& setDo, int r, int c,const vector<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<vector>& cells) { m_c = col; int iMaskNum = row * col; vector<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; };
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17