《Java实现 LeetCode 1162 地图分析（可以暴力或者动态规划的BFS）.docx》由会员分享，可在线阅读，更多相关《Java实现 LeetCode 1162 地图分析（可以暴力或者动态规划的BFS）.docx（3页珍藏版）》请在金锄头文库上搜索。
1、Java实现 LeetCode 1162 地图分析（可以暴力或者动态规划的BFS）1162. 地图分析你现在手里有一份大小为 N x N 的地图（网格） grid，上面的每个区域（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。（PS：你看看这个翻译）我们这里说的距离是曼哈顿距离（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。如果我们的地图上只有陆地或者海洋，请返回 -1。示例
2、1：输入：1,0,1,0,0,0,1,0,1输出：2解释：海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。示例 2：输入：1,0,0,0,0,0,0,0,0输出：4解释：海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。提示：1 = grid.length = grid0.length = 100gridij 不是 0 就是 1class Solution public int maxDistance(int grid) int m=grid.length; int n=grid0.length; boolean f=false; /从两个
3、方法查询，并且是正反查询 for(int i=0;im;i+) for(int j=0;j0) gridij=Math.min(gridij,gridi-1j+1); if(j0) gridij=Math.min(gridij,gridij-1+1); int res=0; for(int i=m-1;i=0;i-) for(int j=n-1;j=0;j-) if(gridij=1) continue; if(im-1) gridij=Math.min(gridij,gridi+1j+1); if(jn-1) gridij=Math.min(gridij,gridij+1+1); /他需要的是最远的距离中最近的 res=Math.max(res,gridij); return f?res-1:-1;
