算法 c++ 并集查找 【二分查找】LeetCode1970:你能穿过矩阵的最后一天

本文涉及的基础知识点

二分查找算法合集

作者推荐

动态规划LeetCode2552：优化了6版的1324模式

题目

给你一个下标从 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 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> GetNodeOfRegion()

{

std::unordered_map> 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 latestDayToCross(int row, int col, vector>& 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> mat(row, vector(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

好文链接