C++ binary algorithm: swimming in a swimming pool with rising water level

Involving knowledge points

Binary search Union search or BFS.

Title

In an n x n integer matrix grid, the value of each square grid[i][j] represents the height of the platform at position (i, j).
When it starts to rain, at time t, the water level in the pool is t. You can swim from one platform to any adjacent platform, but the prerequisite is that the water level must cover both platforms at the same time. Assume that you can move an infinite distance instantly, which means that by default, swimming inside the square is time-consuming. Of course, you must stay within the grid while you swim.
You start from the upper left platform (0,0) of the coordinate grid. Returns the minimum time it takes for you to reach the lower right platform (n-1, n-1) of the coordinate grid.
Example 1:
Input: grid = [[0,2],[1,3]]
Output: 3
explain:
When time is 0, your position on the coordinate grid is (0, 0).
You cannot swim in any direction at this time because the heights of the four adjacent platforms are greater than the water level at the current time of 0.
When the time reaches 3, you can swim to the platform (1, 1). Because the water level at this time is 3, there is no platform higher than the water level 3 in the coordinate grid, so you can swim to the platform in the coordinate grid. Anywhere
Example 2:
Input: 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]]
Output: 16
Explanation: The final route is marked in bold.
We have to wait until time 16 before we can guarantee that platforms (0, 0) and (4, 4) are connected
Parameter range
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
Each value in grid[i][j] has no duplicates

Analysis

Time complexity

O(log(nn)nn). The time complexity of binary search is O(log(nn)), and the time complexity of the Can function is about O(n*n).

Can function

At time t, whether the starting point and the end point are connected. Two adjacent single cells grid[r][c] and grid[r1][c1] are connected if they are both less than or equal to t. Use union search or BFS to determine whether the starting point and end point are connected. You only need to determine the right and downward paths. The left and upward paths must have corresponding right or downward paths.

Two points

If at time t, the requirements are met; then t + 1 must be met. Corresponding to the t that meets the requirements, we need to find the minimum value. Therefore, using a left-open and right-closed space, the value range of t is [0, nn-1], and a left-open and right-closed space is (-1, nn-1]

Error-prone points

for (int r = 0; r < m_c; r + + )

r < m_c cannot be written as r + 1 The calculation mask is encapsulated into a function to reduce errors.

Code

Core code

classCUionFind
{
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()//The number of nodes in each Unicom region
{
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;//The index of the connected area where each point is located, the index of any point in this connected area, in order to increase the understandability, use the minimum index
int m_iConnetRegionCount;
};

class Solution {
public:
int swimInWater(vector & amp; 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 & amp; 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 {
uf.Union(Mask(r,c), Mask(r, c + 1));
}
if ((r + 1 < m_c) & amp; & amp; (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;
};

Test cases

template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}

template
void Assert(const vector & amp; v1, const vector & amp; 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 grid;
int res = 0;
{
Solution slug;
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 = slug.swimInWater(grid);
Assert(16, res);
}
{
Solution slug;
grid = { {0,2},{1,3} };
res = slug.swimInWater(grid);
Assert(3, res);
}

//CConsole::Out(res);
}

Old code in March 2023

class Solution {
public:
int swimInWater(vector & amp; 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 & amp; vWater,int t)
{
vector vHasDo(m_r, vector(m_c));
std::queue> 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) & amp; & amp; (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 & amp; vHasDo, std::queue> & amp; queRowCol, const vector & amp; 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;
};

Extended reading

Video course

Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771

If you want to quickly form a battle and share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses
https://edu.csdn.net/lecturer/6176

Related downloads

If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653

What I want to say to you
It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money.
The origin of the Mohist name: everything is recorded in Mohism.
If the program is a one-stop process, then the algorithm is its key point

Test environment

Operating system: win7 Development environment: VS2019 C++ 17
Or Operating system: win10 Development environment: VS2022 C++ 17