你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋,请返回 -1。


class Solution {
    public int maxDistance(int[][] grid) {
        Queue<int[]> queue = new ArrayDeque<>();
        //将所有的陆地加入到队列中
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]==1){
                    queue.add(new int[]{i,j});
                }
            }
        }
        if (queue.size()==0||queue.size()==grid.length*grid.length){
            return -1;
        }
        int res = -1;//初始队列中包含陆地,队列一定不为空
        //寻找距离每个陆地的最远的海洋距离
        while (!queue.isEmpty()){
            res++;//只要存在某个陆地可以遍历到海洋,即可计算
            int n = queue.size();//一层一层的遍历,方便统计距离
            for (int i = 0; i < n; i++) {
                int[] poll = queue.poll();
                //将这个陆地上下左右的海洋都加入队列
                int x= poll[0];
                int y= poll[1];
                if (x-1>=0&&grid[x-1][y]==0){
                    queue.add(new int[]{x-1,y});
                    grid[x-1][y]=2;//避免重复计算
                }
                if (x+1<grid.length&&grid[x+1][y]==0){
                    queue.add(new int[]{x+1,y});
                    grid[x+1][y]=2;//避免重复计算
                }
                if (y-1>=0&&grid[x][y-1]==0){
                    queue.add(new int[]{x,y-1});
                    grid[x][y-1]=2;//避免重复计算
                }
                if (y+1<grid[0].length&&grid[x][y+1]==0){
                    queue.add(new int[]{x,y+1});
                    grid[x][y+1]=2;//避免重复计算
                }
            }
        }
        return res;
    }
}