力扣：地图分析(多源bfs)

题目描述

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
如果网格上只有陆地或者海洋，请返回 -1。
力扣：1162.地图分析
相似题目： 力扣 524. 01矩阵

输入描述

示例：
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

题目分析

根据题中的说明，距离为曼哈顿距离，可以分析出来，每个海洋区域都是同时向周围四个格子扩散。

通过该扩散过程图，就可以很容易的理解 bfs 的过程了

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

        //上下左右
        int[] dx = {-1 , 1 , 0 , 0};
        int[] dy = {0 , 0 , -1 , 1};

        //先将所有的陆地添加到队列
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0 ; i < grid.length ; i ++)
            for(int j = 0 ; j < grid[0].length ; j ++)
                if(grid[i][j] == 1) queue.offer(new int[] {i , j});

        //从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
        boolean hasOcean = false;
        int[] point = null;
        while(!queue.isEmpty()){
            point = queue.poll();
            int x = point[0] , y = point[1];
            for(int i = 0 ; i < 4 ; i ++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length || grid[nx][ny] != 0) continue;
                grid[nx][ny] = grid[x][y] + 1; // 这里我直接修改了原数组，因此就不需要额外的数组来标志是否访问.
                hasOcean = true;
                queue.offer(new int[] {nx, ny});
            }
        }
        // 没有陆地或者没有海洋，返回-1。
        if (point == null || !hasOcean) {
            return -1;
        }
        // 返回最后一次遍历到的海洋的距离。
        return grid[point[0]][point[1]] - 1;
    }
}