BFS算法篇——从晨曦到星辰，BFS算法在多源最短路径问题中的诗意航行（下）-四、地图分析

4.1 题目链接：https://leetcode.cn/problems/as-far-from-land-as-possible/description/

4.2 题目分析：

• 有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
• 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
• 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

4.3 思路讲解：

• 与上题思路基本相同，采取同样策略，将海洋入队列层序遍历即可
• 注意距离的计算方式

4.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    int ret=-1;//最大高度
    int maxDistance(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        vector<vector<int>> dis(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)
                {
                    dis[i][j]=0;
                    q.push({i,j});

                }
            }
        }
        while(q.size())
        {
            
           
                auto [a,b]=q.front();
                q.pop();
                for(int i=0;i<4;i++)
                {
                    int x=a+dx[i],y=b+dy[i];
                    if(x>=0 & x<m && y>=0 && y<n && grid[x][y]==0 && dis[x][y]==-1)
                    {
                        q.push({x,y});
                        dis[x][y]=dis[a][b]+1;
                        ret=max(ret,dis[x][y]);//更新高度
                    }
                }
            

        }
        return ret;

        
    }
};