[多源 bfs]leetcode1162：地图分析(medium)

题目：

题解：

思路：多源 bfs 模板题

• 思路参考AcWing 173. 矩阵距离即可。

代码如下：

using PII = pair;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};// 方向数组
class Solution {
public:
    // 多源 BFS：求的是距离最近1的海洋距离的最大值
    int maxDistance(vector>& g) {
        int n=g.size();
        vector> dist(n,vector(n,-1));
        queue q;
        // 所有陆地作为源点加入
        for(int i=0;ii,j}),dist[i][j]=0;
        // 以下部分与单源BFS没有差别
        int res=-1;
        while(q.size())
        {
            auto [x,y]=q.front();q.pop();
            for(int i=0;i<4;++i){
                int nx=x+dx[i],ny=y+dy[i];
                // 越界或者坐标点已经被访问过了，则进行跳过
                if(nx<0||ny<0||nx>=n||ny>=n||dist[nx][ny]!=-1)continue;
                // 更新距离并加入队列
                dist[nx][ny]=dist[x][y]+1;
                res=max(res,dist[nx][ny]);
                q.push({nx,ny});
            }
        }
        return res;
    }
};