从Leetcode 每日一题练习继续讨论：
1765. 地图中的最高点
1765. Map of Highest Peak
题解
本题要读懂题面，注意要求相邻两个格子的差值最多为1，而水面的高度必须为0，则以水面为基准，水面的相邻格子高度必定为0或者1，为了最终能得到尽可能大的最大值，必然要选择让水面相邻格子的高度增加即均为1，对于得到的全部高度为1的的格子，同样对这些格子的相邻格子由于题面限制，这些格子的相邻格子的高度必定为2，以此迭代直到全部格子都被填满，最后被填充的格子的高度即为得到的最大高度。
则此过程可以使用bfs来解决，先将所有的水面位置放入队列，再依次执行bfs，将所有水面的相邻位置高度设为1并放入队列，继续对高度为1的格子执行bfs，以此类推。
代码
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m = isWater.size();
int n = isWater[0].size();
vector<vector<int>> height(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isWater[i][j] == 1) {
height[i][j] = 0;
q.push({i, j});
}
}
}
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};
// BFS过程
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
height[nx][ny] = height[x][y] + 1;
q.push({nx, ny});
}
}
}
return height;
}
};