1162. 地图分析 - 力扣（LeetCode）1162. 地图分析 - 你现在手里有一份大小为 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(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); vector<vector<int>> ret(m,vector<int> (n,-1)); queue<pair<int ,int>>q; for(int i=0;i<m;i++) { for(int j=0;j<n;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 i=0;i<4;i++) { int x=a+dx[i]; int y=b+dy[i]; if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==0&&ret[x][y]==-1) { ret[x][y]=ret[a][b]+1; q.push({x,y}); } } } int ans=-2; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { ans=ret[i][j]>ans?ret[i][j]:ans; } } return ans == 0 ? -1 : ans; } };
)