【广度优先搜索】【堆】【C++算法】407. 接雨水 II

作者推荐

【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

本文涉及知识点

广度优先搜索 堆

LeetCoce407. 接雨水 II

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
示例 1:
在这里插入图片描述

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
示例 2:
在这里插入图片描述

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10
提示:
m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104

广度优先搜索

vHeight记录各单格包括水的高度，初始为-1，表示未处理。四周边界显然无法留住水，所以四周边界的vHeight等于heightMap。
不断处理vHeight最小单格(r,c)的邻接单格(nr,nc) vHeight[nr][nc] = max(vHeight[r][c],heightMap[nr][nc]。
边界全部在已处理格子中。
{ 不会做什么 已处理格子的邻居都已经处理 不是边界 处理邻居 已处理格子有邻居未处理 边界

{不会做什么已处理格子的邻居都已经处理不是边界处理邻居已处理格子有邻居未处理边界
{不会做什么处理邻居​已处理格子的邻居都已经处理已处理格子有邻居未处理​不是边界边界​
假定h1是边界最低vHeight，则任意未处理单格的水达到h1时，都不会流出。
h1所在单格的邻居水不会超过h1，否则会流到h1所在单格。

代码

核心代码

class CEnumGridEdge
{
public:
	void Init()
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
	}
	const int m_r, m_c;
protected:
	CEnumGridEdge(int r, int c) :m_r(r), m_c(c)
	{

	}
	void Move(int preR, int preC, int r, int c)
	{
		if ((r < 0) || (r >= m_r))
		{
			return;
		}
		if ((c < 0) || (c >= m_c))

		{
			return;
		}
		OnEnumEdge(preR, preC, r, c);
	};
	virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0;
};

class TNeiBoForGrid : public CEnumGridEdge
{
public:
	TNeiBoForGrid(const vector<vector<int>>& grid) :m_grid(grid),
		CEnumGridEdge(grid.size(), grid.front().size())
	{
		m_vNext.assign(m_r, vector < vector<pair<int, int>>>(m_c));
		Init();
	}
	virtual void OnEnumEdge(int preR, int preC, int r, int c)
	{	
		m_vNext[preR][preC].emplace_back(r, c);
	}
	const vector<vector<int>>& m_grid;
	vector < vector < vector<pair<int, int>>>> m_vNext;
};
class Solution {
public:
	int trapRainWater(vector<vector<int>>& heightMap) {
		TNeiBoForGrid neiBo(heightMap);
		vector<vector<int>> vHeight(neiBo.m_r, vector<int>(neiBo.m_c, -1));
		priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> minHeap;
		auto Add = [&](int r, int c, int iHeight)
		{
			if (vHeight[r][c] >= 0)
			{
				return;
			}
			vHeight[r][c] = iHeight;
			minHeap.emplace(iHeight, r, c);
		};
		for (int r = 0; r < neiBo.m_r; r++)
		{
			for (int c = 0; c < neiBo.m_c; c++)
			{
				if ((0 == r) || (neiBo.m_r == r + 1) || (0 == c) || (neiBo.m_c == c + 1))
				{
					Add(r, c, heightMap[r][c]);
				}
			}
		}
		while (minHeap.size())
		{
			auto [height, r, c] = minHeap.top();
			minHeap.pop();
			for (const auto& [nr, nc] : neiBo.m_vNext[r][c])
			{
				Add(nr, nc, max(height, heightMap[nr][nc]));
			}
		}
		int iRet = 0;
		for (int r = 0; r < neiBo.m_r; r++)
		{
			iRet += std::accumulate(vHeight[r].begin(), vHeight[r].end(), 0) - std::accumulate(heightMap[r].begin(), heightMap[r].end(), 0);
		}
		return iRet;
	}

};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

测试用例

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

template<class T>
void Assert(const vector<T>& v1, const vector<T>& 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<vector<int>> heightMap;
	{
		Solution sln;
		heightMap = { {1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1} };
		auto res = sln.trapRainWater(heightMap);
		Assert(4, res);
	}
	
	{
		Solution sln;
		heightMap = { {3,3,3,3,3},{3,2,2,2,3},{3,2,1,2,3},{3,2,2,2,3},{3,3,3,3,3} };
		auto res = sln.trapRainWater(heightMap);
		Assert(10, res);
	}

	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

2023年3月

class Solution {
public:
int trapRainWater(vector& heightMap) {
m_r = heightMap.size();
m_c = heightMap[0].size();
//memset(m_arrNeiNum, 4, sizeof(m_arrNeiNum));
for (int c = 0; c < m_c; c++)
{
//m_arrNeiNum[0][c] = 1;
//m_arrNeiNum[m_r - 1][c] = 1;
AddRowColToRange(0, c, heightMap);
AddRowColToRange(m_r-1, c, heightMap);
}
for (int r = 1; r + 1 < m_r; r++)
{
AddRowColToRange(r,0, heightMap);
AddRowColToRange(r,m_c-1, heightMap);
//m_arrNeiNum[r][0] = 1;
//m_arrNeiNum[r][m_c - 1] = 1;
}
while (m_mHeightRowCol.size())
{
const int iHeight = m_mHeightRowCol.begin()->first;
const int r = m_mHeightRowCol.begin()->second / 1000;
const int c = m_mHeightRowCol.begin()->second % 1000;
Add(r + 1, c, iHeight,heightMap);
Add(r - 1, c, iHeight, heightMap);
Add(r, c + 1, iHeight, heightMap);
Add(r, c - 1, iHeight, heightMap);
m_mHeightRowCol.erase(m_mHeightRowCol.begin());
}
return m_iRet;
}
void Add(int r, int c, int iPreHeight, const vector& heightMap)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (m_setHasDo.count(RowColMask(r,c)))
{
return;
}
const int iCurHeight = heightMap[r][c];
const int iWaterHeight = max(iCurHeight, iPreHeight);
if (iWaterHeight > iCurHeight)
{
m_iRet += iWaterHeight - iCurHeight;
}
AddRowColToRange(r, c, iWaterHeight);
}
void AddRowColToRange(int r, int c, const int iWaterHeight)
{
const int iRowCol = RowColMask(r, c);
m_mHeightRowCol.emplace(iWaterHeight, iRowCol);
m_setHasDo.insert(iRowCol);
}
void AddRowColToRange(int r, int c,const vector& heightMap)
{
AddRowColToRange(r, c, heightMap[r][c]);
}
inline int RowColMask(int r, int c)
{
return 1000 * r + c;
}
int m_r;
int m_c;
std::multimap m_mHeightRowCol;//记录当前边界
std::unordered_set m_setHasDo;//记录已经处理的格子
std::unordered_set m_setNeiHasDo;//记录相邻格子已经处理完毕
//char m_arrNeiNum[200][200];//记录邻居数
int m_iRet = 0;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136182623"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！