【[C++BFS】1765. 地图中的最高点

本文涉及知识点

C++BFS算法

LeetCoce1765. 地图中的最高点

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由陆地和水域单元格组成的地图。
如果 isWater[i][j] == 0 ，格子 (i, j) 是一个陆地格子。
如果 isWater[i][j] == 1 ，格子 (i, j) 是一个水域格子。
你需要按照如下规则给每个单元格安排高度：
每个格子的高度都必须是非负的。
如果一个格子是水域，那么它的高度必须为 0 。
任意相邻的格子高度差至多为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
找到一种安排高度的方案，使得矩阵中的最高高度值最大。
请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回任意一个。
示例 1：
在这里插入图片描述

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。
示例 2：
在这里插入图片描述

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

提示：
m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] 要么是 0 ，要么是 1 。
至少有 1 个水域格子。

C++BFS

BFS的预处理：陆地更改成-1，水域更改为0。
BFS的初始状态：leves[0] = {所有水域单格}。
BFS的状态表示：leves[i]记录任意水域的最近距离为i的陆地。
BFS的后续状态：通过next访问cur的四连通临接点。
BFS的返回值：grid。
BFS的重复处理：利用grid做重复处理。grid[r][c]为-1，表示未处理。

正确性证明

从小到处理leves[i]。
i为1是，因为和水域相邻，故最大为1。由于已处理的单格和当前单格相邻的一定是leves[0]和leves[1]故为1，不会冲同。
$\vdots$
leves[i]和leves[i-1]相邻，故最大为i。和已经处理单格相邻的只会是leves[i]和leves[i-1]，故不会冲突。

代码

核心代码

class CGrid {
public:CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}vector<vector<pair<int, int>>> NeiBo(std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4){vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);auto Move = [&](int preR, int preC, int r, int c){if ((r < 0) || (r >= m_r)){return;}if ((c < 0) || (c >= m_c)){return;}if (funVilidCur(preR, preC) && funVilidNext(r, c)){vNeiBo[Mask(preR, preC)].emplace_back(r, c);}};for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){for (int k = 0; k < iConnect; k++){Move(r, c, r + s_Moves[k][0], c + s_Moves[k][1]);}}}return vNeiBo;}void EnumGrid(std::function<void(int, int)> call){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){call(r, c);}}}inline int Mask(int r, int c) { return  m_c * r + c; }const int m_r, m_c;const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};class Solution {public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {queue<pair<int, int>> que;CGrid ng(isWater.size(), isWater[0].size());ng.EnumGrid([&](int r, int c) {if (1 == isWater[r][c]) {isWater[r][c] = 0;que.emplace(r, c);}else {isWater[r][c] = -1;}});auto neiBo = ng.NeiBo([](int r, int c) {return true; }, [&](int r, int c) {return 0 != isWater[r][c]; });				while (que.size()) {const auto [r, c] = que.front();que.pop();for (const auto& [r1, c1] : neiBo[ng.Mask(r, c)]) {if (-1 == isWater[r1][c1]) {isWater[r1][c1] = isWater[r][c] + 1;que.emplace(r1, c1);}}}return isWater;}};

单元测试

	vector<vector<int>> isWater;void Check(const vector<vector<int>>& res, const vector<vector<int>>& isWater,int iMax){Assert::AreEqual((int)res.size(), (int)isWater.size());Assert::AreEqual((int)res[0].size(), (int)isWater[0].size());int iActMax = 0;for (int r = 0; r < res.size(); r++) {iActMax = max(iActMax, *std::max_element(res[r].begin(),res[r].end()));for (int c = 0; c < res[0].size(); c++) {if (0 == isWater[r][c]) {Assert::AreEqual(0, res[r][c]);						}if (r > 0) {Assert::IsTrue(abs(res[r][c] - res[r - 1][c]) <= 1);}if (c > 0) {Assert::IsTrue(abs(res[r][c] - res[r][c - 1]) <= 1);}}}		}TEST_METHOD(TestMethod1){isWater = { {1} };auto res = Solution().highestPeak(isWater);Check(res, isWater,0);}TEST_METHOD(TestMethod2){isWater = { {1,0,0,0,0} };auto res = Solution().highestPeak(isWater);Check(res, isWater, 4);}TEST_METHOD(TestMethod3){isWater = { {1,0,0,0,1} };auto res = Solution().highestPeak(isWater);Check(res, isWater, 2);}TEST_METHOD(TestMethod11){isWater = { {0,1},{0,0} };auto res = Solution().highestPeak(isWater);Check(res, isWater,2);}TEST_METHOD(TestMethod12){isWater = { {0,0,1},{1,0,0},{0,0,0} };auto res = Solution().highestPeak(isWater);Check(res, isWater,2);}

使用模板代码

class CGrid {
public:CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}vector<vector<pair<int, int>>> NeiBo(std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4){vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);auto Move = [&](int preR, int preC, int r, int c){if ((r < 0) || (r >= m_r)){return;}if ((c < 0) || (c >= m_c)){return;}if (funVilidCur(preR, preC) && funVilidNext(r, c)){vNeiBo[Mask(preR, preC)].emplace_back(r, c);}};for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){for (int k = 0; k < iConnect; k++){Move(r, c, r + s_Moves[k][0], c + s_Moves[k][1]);}}}return vNeiBo;}void EnumGrid(std::function<void(int, int)> call){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){call(r, c);}}}inline int Mask(int r, int c) { return  m_c * r + c; }const int m_r, m_c;const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};class Solution {public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {queue<pair<int, int>> que;CGrid ng(isWater.size(), isWater[0].size());ng.EnumGrid([&](int r, int c) {if (1 == isWater[r][c]) {isWater[r][c] = 0;que.emplace(r, c);}else {isWater[r][c] = -1;}});auto neiBo = ng.NeiBo([](int r, int c) {return true; }, [&](int r, int c) {return 0 != isWater[r][c]; });				while (que.size()) {const auto [r, c] = que.front();que.pop();for (const auto& [r1, c1] : neiBo[ng.Mask(r, c)]) {if (-1 == isWater[r1][c1]) {isWater[r1][c1] = isWater[r][c] + 1;que.emplace(r1, c1);}}}return isWater;}};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。