算法提高课-搜索-多源BFS-AcWing 173. 矩阵距离：bfs、多源bfs

题目分析

来源：acwing

分析：
0表示住户，1表示超市，这些超市是等价的。求每个住户到达超市的最近距离。

多源bfs在做的时候，把所有超市的距离都初始化为0，然后压入队列。

这里用的是数组模拟队列，没用queue。 在将所有超市压入队列之前，hh = 0， tt = -1

然后就是普通的宽搜模板，默写上即可。

ac代码

#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N = 1010, M = N * N; int n, m; char g[N][N]; PII q[M]; int dist[N][N];void bfs(){memset(dist, -1, sizeof dist);int hh = 0, tt = -1;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(g[i][j] == '1'){q[++tt] = {i, j};dist[i][j] = 0;}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};while(hh <= tt){PII t = q[hh ++];for(int i = 0; i < 4; i ++){int a = t.x + dx[i], b= t.y + dy[i];if( a < 0 || a >= n || b < 0 || b >= m) continue;if(dist[a][b] != -1) continue; // 如果遍历过，则跳过dist[a][b] = dist[t.x][t.y] + 1;q[++tt] = {a,b};}}}int main(){cin >> n >> m;for(int i = 0; i < n; i ++) cin >> g[i];bfs();for(int i = 0; i < n; i ++){for(int j = 0; j< m; j ++)cout << dist[i][j] << " ";cout << endl;} }

题目来源

https://www.acwing.com/problem/content/175/

总结

以上是生活随笔为你收集整理的算法提高课-搜索-多源BFS-AcWing 173. 矩阵距离：bfs、多源bfs的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。