---

1765.地图中的最高点

题目描述

地图中的最高点

---

思路

多源BFS

根据题意，要求让矩阵中的最高高度最大，那么就需要最大化每个格子的高度才能实现。因为任意相邻的格子高度至多差1，这意味着每个格子的高度至多比周围的所有相邻格子中的最小高度多1。
另外题目要求水域的高度必须为0，因此水域的高度是已知的，那么就可以从水域出发，推导出其余格子的高度：

• 首先，计算与水域相邻的格子的高度。这些格子其相邻格子的最小高度即为水域的高度0，所以这些格子高度为1。
• 然后，计算与高度为1的格子相邻的、且未被计算过的格子的高度。这些格子相邻格子最小高度为1，因此这些格子的高度为2。
• 以此类推，计算出所有格子的高度。
  所以，上述过程就是从水域出发，执行BFS的过程。因此，记录下所有水域的位置，然后进行BFS，计算出所有陆地格子的高度，即为答案。

Java实现

class Solution {int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] ans = new int[m][n];for (int i = 0; i < m; ++i) {Arrays.fill(ans[i], -1); // -1 表示该格子尚未被访问过}Queue<int[]> queue = new ArrayDeque<int[]>();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (isWater[i][j] == 1) {ans[i][j] = 0;queue.offer(new int[]{i, j}); // 将所有水域入队}}}while (!queue.isEmpty()) {int[] p = queue.poll();for (int[] dir : dirs) {int x = p[0] + dir[0], y = p[1] + dir[1];if (0 <= x && x < m && 0 <= y && y < n && ans[x][y] == -1) {ans[x][y] = ans[p[0]][p[1]] + 1;queue.offer(new int[]{x, y});}}}return ans;}
}

Python实现

class Solution:def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:m, n = len(isWater), len(isWater[0])ans = [[water - 1 for water in row] for row in isWater]q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)while q:i, j = q.popleft()for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:ans[x][y] = ans[i][j] + 1q.append((x, y))return ans