1162. 地图分析 - 力扣LeetCode1162. 地图分析 - 你现在手里有一份大小为 n x n 的 网格 grid上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋1 代表陆地。请你找出一个海洋单元格这个海洋单元格到离它最近的陆地单元格的距离是最大的并返回该距离。如果网格上只有陆地或者海洋请返回 -1。我们这里说的距离是「曼哈顿距离」 Manhattan Distance(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| |y0 - y1| 。 示例 1[https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/08/17/1336_ex1.jpeg]输入grid [[1,0,1],[0,0,0],[1,0,1]]输出2解释 海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大最大距离为 2。示例 2[https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/08/17/1336_ex2.jpeg]输入grid [[1,0,0],[0,0,0],[0,0,0]]输出4解释 海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大最大距离为 4。 提示 * n grid.length * n grid[i].length * 1 n 100 * grid[i][j] 不是 0 就是 1https://leetcode.cn/problems/as-far-from-land-as-possible/description/一、题目描述给定一个n * n的网格地图grid里面1代表陆地0代表海洋我们需要找到距离陆地最远的海洋格子的距离。距离定义该海洋格子到最近一块陆地的曼哈顿距离。特殊情况全陆地 / 全海洋 → 输出-1最优思路多源 BFS核心多源 BFS 本质所有起点同时扩散一层一层向外“淹”本题所有陆地都是源点先把所有陆地一次性入队距离初始化为 0队列统一向外四层扩散第一次访问到海洋的距离就是该海洋到最近陆地的最短距离初始化距离数组ret全部置-1未访问遍历网格将所有陆地入队距离置 0开始 BFS 四层扩散只访问未访问的海洋遍历距离数组找出最大距离特判最大距离为 0全陆地返回 -1否则返回最大距离class Solution { public: int dx[4]{0,0,1,-1}; int dy[4]{1,-1,0,0}; int maxDistance(vectorvectorint grid) { int mgrid.size(); int ngrid[0].size(); vectorvectorint ret(m,vectorint (n,-1)); queuepairint ,intq; for(int i0;im;i) { for(int j0;jn;j) { if(grid[i][j]1) { q.push({i,j}); ret[i][j]0; } } } while(q.size()) { auto [a,b]q.front();q.pop(); for(int i0;i4;i) { int xadx[i]; int ybdy[i]; if(x0xmy0yngrid[x][y]0ret[x][y]-1) { ret[x][y]ret[a][b]1; q.push({x,y}); } } } int ans-2; for(int i0;im;i) { for(int j0;jn;j) { ansret[i][j]ans?ret[i][j]:ans; } } return ans 0 ? -1 : ans; } };