【多源BFS问题】地图中的最高点 && 地图分析
【多源BFS问题】地图中的最高点 && 地图分析
1765. 地图中的最高点
给你一个大小为 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.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j]要么是0，要么是1。- 至少有 1 个水域格子。
解题思路：多源BFS
这道题其实和 542. 01 矩阵 基本是一样的，只不过那道题中要将元素为 0 的位置作为源点，而 这道题将元素为 1 的位置作为源点，其它都是一致的，这里不再赘述，具体可以参考那道题的笔记！
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> distance(m, vector<int>(n, -1)); // 初始化距离矩阵为-1
// 将所有水域位置加入队列中，并且距离矩阵中置为0
queue<pair<int, int>> bfs;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(isWater[i][j] == 1)
{
bfs.push({i, j});
distance[i][j] = 0;
}
}
}
// 多源bfs，需要一层一层向外拓展
while(!bfs.empty())
{
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
if(newx >= 0 && newy >= 0 && newx < m && newy < n && distance[newx][newy] == -1)
{
bfs.push({newx, newy});
distance[newx][newy] = distance[x][y] + 1;
}
}
}
}
return distance;
}
};1162. 地图分析
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例 1：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。示例 2：
输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。提示：
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]不是0就是1
解题思路：多源BFS
这道题同样是 542. 01 矩阵 这道题的变形，虽然题目中说曼哈顿距离，需要有两个距离最远的坐标，但其实我们并不需要知道其坐标，只需要知道它的距离即可，为什么呢❓❓❓
其实曼哈顿距离的公式就暗示我们了，两个 x 坐标和两个 y 坐标的距离相加，其实就是在矩阵中两个坐标，只能通过上下左右移动时候走的最短距离！如下图所示：
也就是说这道题其实和 542. 01 矩阵 是一模一样的，我们只需要用一个 distance 表和多源 bfs 来计算出矩阵中 0 和 1 的最远距离即可，这就是最后要求的曼哈顿距离，而不需要说用两个下标去做计算了！
代码几乎是一模一样的，如下所示：
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
public:
int maxDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> distance(m, vector<int>(n, -1)); // 创建并且初始化距离表为-1
// 1. 以1作为源点，将它们都加入队列中，然后修改距离为0
queue<pair<int, int>> bfs;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 1)
{
bfs.push({i, j});
distance[i][j] = 0;
}
}
}
// 2. 进行多源bfs操作，需要一层一层向外拓展
int ret = -1;
while(!bfs.empty())
{
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
if(newx >= 0 && newy >= 0 && newx < m && newy < n && distance[newx][newy] == -1)
{
bfs.push({newx, newy});
distance[newx][newy] = distance[x][y] + 1;
ret = max(ret, distance[newx][newy]); // 别忘了更新最大值
}
}
}
}
return ret; // 如果只有陆地或者海洋的话，那么上面就不会更新ret，就还是-1
}
};腾讯云开发者
