LeetCode 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]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。method: 多源BFS
每个0的位置可以向四周扩展出1，1又能向4周扩展出2，以此类推
int next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> grid(m, vector<int>(n, -1)); // 初始化为-1
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isWater[i][j]) {
grid[i][j] = 0; // 水域的位置为0
q.push({i, j}); // 加入到队列中
}
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + next[k][0];
int ny = y + next[k][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == -1) {
grid[nx][ny] = grid[x][y] + 1; // 扩展1次就加1
q.push({nx, ny});
}
}
}
return grid;
}994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4method: 多源BFS
int next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int cnt = 0;
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) cnt++; // 统计新鲜橘子
else if (grid[i][j] == 2) q.push({i, j}); // 烂橘子入队
}
}
if (cnt == 0) return 0; // 没有烂橘子
int res = -1; // 如果初始化为0，最后的烂橘子出队时也会res+1，但出队前已经全为烂橘子了，所以还要res-1，干脆初始化为-1
while (!q.empty()) {
int size = q.size(); // 先记录这次又多少需要出队
for (int i = 0; i < size; i++) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + next[k][0];
int ny = y + next[k][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
cnt--; // 新鲜橘子减少，变成烂橘子入队
grid[nx][ny] = 2;
q.push({nx, ny});
}
}
}
res++; // 这一次的全出队，表示扩展一层，即过了1分钟
}
return cnt == 0 ? res : -1;
}
