LeetCode 1162. 地图分析 (Java版; Meidum)

Bertha 。 2023-07-18 14:19 11阅读 0赞

### [welcome to my blog][] ###

## LeetCode 1162. 地图分析 (Java版; Meidum) ##

#### 题目描述 ####

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，
    你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
    
    我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
    
    如果我们的地图上只有陆地或者海洋，请返回 -1。
    
    
    示例 1：

![format_png][]

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

![format_png 1][]

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

#### 第一次做; BFS 核心:1)从陆地开始蔓延, 将当前层的陆地都进行扩展, 然后将遇到的区域都变成陆地并加入队列, 就这样一层一层地扩展, 扩展一次, res++; 直到最后一次, 无法再扩展, 说明此时全是陆地了, 返回res - 1, 减一是因为最后一次没有扩展, 但还是多加了个1, 将这个1抵消掉 ####

class Solution { 
        public int maxDistance(int[][] grid) { 
            //BFS; 一层一层的BFS
            int n = grid.length, m = grid[0].length;
            //记录陆地的队列
            LinkedList<int[]> queue = new LinkedList<>();
            for(int i=0; i<m; i++){ 
                for(int j=0; j<n; j++){ 
                    if(grid[i][j]==1){ 
                        queue.add(new int[]{ i,j});
                    }
                }
            }
            //如果全是海洋或者全是陆地
            if(queue.size()==0 || queue.size()==m*n){ 
                return -1;
            }
            //二维数组; 控制上下左右移动
            int[][] moves = { { -1,0}, { 1,0}, { 0,-1}, { 0,1}};
            int res=0;
            //BFS
            while(!queue.isEmpty()){ 
                //核心: 当前层的节点数; 需要弹出当前层的所有节点, 但是不能弹出新加入的节点
                int count = queue.size();
                for(int i=0; i<count; i++){ 
                    int[] cur = queue.poll();
                    int x, y;
                    for(int[] move : moves){ 
                        x = cur[0] + move[0];
                        y = cur[1] + move[1];
                        if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==0){ 
                            grid[x][y] = 1;
                            queue.add(new int[]{ x,y});
                        }
                    }
                }
                res++;
            }
            return res-1;
    
        }
    }

#### 第一次做; 暴力, 超时17/35 核心: 1) 分别记录所有的海洋和陆地, 遍历海洋, 记录当前海洋距离所有陆地的最小值; 在所有的最小值中找到最大值 ####

class Solution { 
        public int maxDistance(int[][] grid) { 
            //暴力
            int n = grid.length, m = grid[0].length;
            boolean ocean = true, land = true;
            HashSet<int[]> oceanSet = new HashSet<>();
            HashSet<int[]> landSet = new HashSet<>();
            for(int i=0; i<m; i++){ 
                for(int j=0; j<n; j++){ 
                    if(grid[i][j]==0){ 
                        oceanSet.add(new int[]{ i,j});
                        land = false;
                    }else{ 
                        landSet.add(new int[]{ i,j});
                        ocean = false;
                    }
                }
            }
            if(ocean || land){ 
                return -1;
            }
            int res = 1;
            for(int[] oce : oceanSet){ 
                int i = oce[0], j = oce[1];
                int min = Integer.MAX_VALUE;
                for(int[] lan : landSet){ 
                    min = Math.min(min, Math.abs(i-lan[0])+Math.abs(j-lan[1]));
                }
                res = Math.max(res, min);
            }
            return res;
    
        }
    }

#### \[力扣优秀题解(https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/zhen-liang-yan-sou-huan-neng-duo-yuan-kan-wan-miao/) 图示非常棒, 多源BFS ####

[welcome to my blog]: https://littlehaes.com
[format_png]: /images/20230528/a039f3e37c99402db6a0fcf6eee9b53e.png
[format_png 1]: /images/20230528/2a3f065a286b42888de9658c1cd2ec14.png