🗺️ 地图分析

📝 题目描述

​ 你现在手里有一份大小为n x n的网格grid，上面的每个单元格都用0和1标记好了。其中0代表海洋，1代表陆地。

​ 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回-1。

​ 我们这里说的距离是「曼哈顿距离」（Manhattan Distance）：(x0, y0)和(x1, y1)这两个单元格之间的距离是|x0-x1| + |y0-y1|。

📋 代码模板

java

class Solution {
    public int maxDistance(int[][] grid) {

    }
}

typescript

function maxDistance(grid: number[][]): number {
    
}

💡 提示

1. $n==grid.length$
2. $n==grid[i].length$
3. $1\le n\le 100$
4. $grid[i][j]$ 不是 $0$ 就是 $1$

🚀 示例

示例一

​ 输入grid为[[1,0,1],[0,0,0],[1,0,1]]，输出为2。如下图所示，海洋单元格(1,1)距离最近的陆地单元格(0,0)距离最大（不是唯一的最优解）。

示例二

​ 输入grid为[[1,0,0],[0,0,0],[0,0,0]]，输出为4。如下图所示，海洋单元格(2,2)距离最近的陆地单元格(0,0)距离最大。

示例三

​ 输入grid为[[1,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]，输出为9。如下图所示，海洋单元格(5,5)距离最近的陆地单元格(0,1)距离最大。

🖊️ 题解

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

1. 初始化一个值为 $0$ 的变量 $level$ 用于记录BFS层数，并创建一个用于BFS的队列。
2. 遍历整个网格，将每个陆地单元格（值为 $1$​）作为源点加入队列中。
3. 如果队列中源点的个数为 $n^2$ 或 $0$，那么说明网格中只有陆地或者海洋，此时应直接返回 $-1$。
4. 同时从所有源点开始进行BFS，逐层向四周扩散，如果搜索到尚未访问的海洋单元格（值为 $0$），则将它的状态设为”已访问“。在BFS过程中，我们需要维护变量 $level$，值为当前搜索的层数。为了进一步节省算法的空间，我们可以直接将网格中单元格的值更新为 $2$，表示其已经被访问。
5. BFS结束后，返回 $level-1$。

java

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

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        if (queue.size() == n * n || queue.size() == 0) {
            return -1;
        }
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                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 > n - 1 || j < 0 || j > n - 1 || grid[i][j] != 0) {
                        continue;
                    }
                    queue.offer(new int[]{i, j});
                    grid[i][j] = VISITED;
                }
                size--;
            }
            level++;
        }
        return level - 1;
    }
}

typescript

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

function maxDistance(grid: number[][]): number {
    const n = grid.length;
    const queue: number[][] = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                queue.push([i, j]);
            }
        }
    }
    if (queue.length == n * n || queue.length == 0) {
        return -1;
    }
    let level = 0;
    while (queue.length > 0) {
        let size = queue.length;
        while (size > 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 > n - 1 || j < 0 || j > n - 1 || grid[i][j] != 0) {
                    continue;
                }
                queue.push([i, j]);
                grid[i][j] = VISITED;
            }
            size--;
        }
        level++;
    }
    return level - 1;
}

💭 复杂度分析

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

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。