算法沉淀——多源 BFS（leetcode真题剖析）
- 01.矩阵
- 02.飞地的数量
- 03.地图中的最高点
- 04.地图分析
多源 BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的 BFS 中，我们通常从一个起始点开始，逐层遍历所有的相邻节点。而在多源 BFS 中，我们可以同时从多个源点开始，从这些源点出发，逐层向外扩展，直到达到目标或者遍历完整个图。
多源 BFS 可以用于解决一些问题，例如：
- 多个人同时逃生： 在一个迷宫中，有多个人同时被困在不同的位置，需要找到最短路径逃离迷宫。可以从这些人的位置同时开始 BFS，第一个相遇的点就是大家逃生的最短路径。
- 多点到达目标问题： 在一些网络传播或者路由问题中，多个点需要同时到达某个目标点，可以使用多源 BFS 找到最短路径。
- 并行计算： 在一些并行计算的场景中，多源 BFS 可以用于并行地计算多个点到其他点的最短路径。
多源 BFS 的实现方式与单源 BFS 类似，只是需要同时从多个源点开始扩展。通常使用队列来进行层次遍历，每一层表示到达目标的步数。
01.矩阵
题目链接：https://leetcode.cn/problems/01-matrix/
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]] 输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
- m == mat.length
- n == mat[i].length
- 1 const int dx[4]={0,0,1,-1}; const int dy[4]={-1,1,0,0}; public: vector int m=mat.size(),n=mat[0].size(); vector q.push({i,j}); dist[i][j]=0; } while(!q.empty()){ auto [a,b]=q.front(); q.pop(); for(int i=0;i int x=a+dx[i],y=b+dy[i]; if(x=0&&x dist[x][y]=dist[a][b]+1; q.push({x,y}); } } } return dist; } }; const int dx[4]={0,0,1,-1}; const int dy[4]={-1,1,0,0}; int m,n; queue q.push({i,j}); grid[i][j]=0; while(!q.empty()){ int sz=q.size(); while(sz--){ auto [a,b]=q.front(); q.pop(); for(int k=0;k int x=a+dx[k],y=b+dy[k]; if(x=0&&x grid[x][y]=0; q.push({x,y}); } } } } } public: int numEnclaves(vector m=grid.size(),n=grid[0].size(); for(int i=0;i if(grid[i][0]==1) bfs(grid,i,0); if(grid[i][n-1]==1) bfs(grid,i,n-1); } for(int i=1;i if(grid[0][i]==1) bfs(grid,0,i); if(grid[m-1][i]==1) bfs(grid,m-1,i); } int ret=0; for(int i=0;i // 定义四个方向的坐标变化 const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0}; public: int numEnclaves(vector int m = grid.size(), n = grid[0].size(); // 用于标记是否访问过的二维布尔型数组 vector q.push({i, j}); vis[i][j] = true; } // 2. 多源 BFS while (!q.empty()) { auto [a, b] = q.front(); q.pop(); for (int i = 0; i
