文章目录
前言
一、多源BFS
二、AcWing 173. 矩阵距离
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：多源BFS，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、多源BFS
拿例题来讲，本题求的是每一个点距离数字为1的点的最短距离，而一个图中存在多个为1的点，这样来看的话，如果我们和普通的bfs解法一样，只把第一个为1的点放入队列之中去更新其他点的距离的话，显然是不和法的，所以我们要把所有为1的点都加入到队列之中，这种做法，我们称之为多源BFS
二、AcWing 173. 矩阵距离
本题链接：AcWing 173. 矩阵距离
本博客提供本题截图：
本题分析
本题的dist数组除了要负责记录距离，还需要实现判重的功能，具体操作为初始化为-1，因为dist数组要被更新，所以如果一个点的dist的值为-1的话，证明这个点没有被更新，反之则被更新，注意和单源BFS不同的是，我们需要把每一个值为1的点加入到我们的队列中。
AC代码
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; PII q[M]; int dist[N][N]; char g[N][N]; int n, m; void bfs() { memset(dist, -1, sizeof dist); int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0}; int hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (g[i][j] == '1') { dist[i][j] = 0; q[++ tt] = {i, j}; } while (hh <= tt) { auto 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() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); bfs(); for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) printf("%d ", dist[i][j]); puts(""); } return 0; }
三、时间复杂度
关于多源BFS的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
