🏔️ 地图中的最高点

📝 题目描述

​ 给你一个大小为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)的高度。如果有多种解，请返回任意一个。

📋 代码模板

java

class Solution {
    public int[][] highestPeak(int[][] isWater) {

    }
}

typescript

function highestPeak(isWater: number[][]): number[][] {
    
}

💡 提示

1. $m==isWater.length$
2. $n==isWater[i].length$
3. $1\le m\le 1000$
4. $1\le n\le 1000$
5. $isWater[i][j]$ 要么是 $0$，要么是 $1$
6. 至少有 $1$ 个水域格子

🚀 示例

示例一

​ 输入isWater为[[0,1],[0,0]]，输出为[[1,0],[2,1]]。高度安排过程及结果如下图所示。

示例二

​ 输入isWater为[[0,0,1],[1,0,0],[0,0,0]]，输出为[[1,1,0],[0,1,1],[1,2,2]]。高度安排过程及结果如下图所示。

示例三

​ 输入isWater为[[0,0,1,0,1],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]，输出为[[1,1,0,1,0],[0,1,1,2,1],[1,2,2,3,2],[2,3,3,4,3]]。高度安排过程及结果如下图所示。

🖊️ 题解

​ 我们可以利用多源BFS算法来解决该题，具体步骤如下。

1. 创建一个用于记录单元格访问状态的 $m\cdot n$ 大小的二维数组 $visited$ 以及一个用于BFS的队列。
2. 遍历整个矩阵，将每个水域单元格（值为 $1$​）作为源点加入队列中。同时，重设这些水域单元格的值为 $0$，并标记它们的状态为”已访问“。
3. 同时从所有源点开始进行BFS，逐层向四周扩散，如果搜索到尚未访问的陆地单元格（值为 $0$），则重设它的值为移动前（上一次）单元格的值加 $1$，并将它的状态标记为”已访问“。
4. BFS结束后，直接返回 $isWater$，这是因为单元格的高度安排是原地进行的。

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    isWater[i][j] = 0;
                    visited[i][j] = true;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int oldI = cell[0], oldJ = cell[1];
            for (int d = 0; d < 4; d++) {
                int i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visited[i][j]) {
                    continue;
                }
                isWater[i][j] = isWater[oldI][oldJ] + 1;
                queue.offer(new int[]{i, j});
                visited[i][j] = true;
            }
        }
        return isWater;
    }
}

typescript

const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];

function highestPeak(isWater: number[][]): number[][] {
    const m = isWater.length, n = isWater[0].length;
    const visited: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
    const queue: number[][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j] == 1) {
                queue.push([i, j]);
                isWater[i][j] = 0;
                visited[i][j] = true;
            }
        }
    }
    while (queue.length > 0) {
        const cell: number[] = queue.shift()!;
        const oldI = cell[0], oldJ = cell[1];
        for (let d = 0; d < 4; d++) {
            const i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
            if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visited[i][j]) {
                continue;
            }
            isWater[i][j] = isWater[oldI][oldJ] + 1;
            queue.push([i, j]);
            visited[i][j] = true;
        }
    }
    return isWater;
}

💭 复杂度分析

​ 基于多源BFS的解决方案的复杂度分析如下。

• 时间复杂度：$O(mn)$。其中 $m$ 与 $n$ 分别为网格的行数和列数。
• 空间复杂度：$O(mn)$。