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
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
{
std::unordered_map
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
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
{
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
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
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
std::queue
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
{
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