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) 的高度。如果有多种解法，请返回任意一个 。

示例

示例一：

img

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

示例二：

img

输入：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 个水域格子。

解题

根据题意，空间内水面的高度为0，这是确定信息，因此可以从水面的高度出发，向周围迭代计算对应的高度，因为相邻格子的高度差最大为1，所以每个地方只需要迭代一次，并记录第一次访问的高度。

相邻格子可定义为 int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

用队列来控制迭代的顺序（从高度为0的水面开始，然后是高度为1的陆地，依此类推）

刚开始给所有位置赋值 -1 ，表示未访问过该位置，然后遍历，将判定为水面的位置赋值 -1 ，并推入队列。

1
2
3
4
5
// 数组填充
for(int i=0;i<m;i++){
  // 全部填充-1，表示未访问过
  Arrays.fill(ans[i],-1);
}

然后从队列中的水面点开始迭代。每从队列取出一个位置，就计算它的相邻格子，如果相邻格子未访问过（为 -1 ），则设置相邻格子的高度为当前位置 +1，并将该格子推入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
public int[][] highestPeak(int[][] isWater) {
  int m = isWater.length;
  int n = isWater[0].length;
  int[][] ans = new int[m][n];
  
  // 数组填充 -1 ，表示未访问过
  for(int i=0;i<m;i++){
    Arrays.fill(ans[i],-1);
  }
  
  Queue<int[]> queue = new ArrayDeque<>();
  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: directions){
      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;
}