大家好，不同的時間，相同的地點！又和大家見面了，接下來我將帶來多源BFS的內容

通過多源BFS的學習，大家將對BFS理解更加深入！

let's go!

前言

通過前面內容的學習，大家肯定已經對于BFS有了一定理解，但是在某些題目中，我們前面學習的BFS卻不能很好的解決我們的問題。

大家可以想象一下：你從迷宮中心的起點出發，不是孤身一人，而是召集了所有出口的“斥候”同時起跑，他們沿著每一條岔路疾馳，彼此提醒“這條路我已走過”。下一秒，最短的歡呼聲從終點傳來——這就是多源 BFS 的魔法。它讓“單點擴散”瞬間升級為“萬箭齊發”，把最短路問題從“找一條路”變成“聽最早響起的回聲”。讀完這篇博客，你會明白如何讓算法像閃電一樣，從四面八方向答案合圍！

一、多源BFS

1.單源最短路問題 vs 多源最短路問題

1、當問題中只存在一個起點時，這時的最短路問題就是單源最短路問題。

2、當問題中存在多個起點而不是單一起點時，這時的最短路問題就是多源最短路問題。

2.多源BFS

多源最短路問題的邊權都為1的時候，此時就可以用多源BFS來解決。

3.解決方式

把這些源點匯聚在一起時，當成一個“超級源點”。然后從這個“超級源點”開始，處理最短路問題。落實到代碼上就是：

1.初始化的時候，把所有的源點都加入到隊列里面

2.然后正常執行bfs的邏輯即可

也就是在初始化的時候，比普通的bfs多加入幾個起點

二、題目概略

矩陣距離

三、矩陣距離

題目展示：

思路分析：

曼哈頓距離：

對于曼哈頓距離我們有兩種方法來計算：

1.通過坐標計算

2.通過求兩點之間的最短路徑長度來計算

所以我們可以通過BFS來計算其中的最短路徑長度

我們有兩種思路去解決這道題：

1.直接從前往后開始遍歷，找到0，然后通過它來做一次bfs。找到最短路徑長度
弊端：時間復雜度很高

2.正難則反，我們去找1，將這些1當做一個大源點，然后去找0，找到了就更新對應的距離。做一次BFS就可以解決

在這里，我就實現第二種方法了：

如何存放矩陣？

由于只存放1,0這種數，我們使用一個char a[][]的數組來存放數據即可。

如何存放最短距離？

再使用一個int dist[N][N]；來存放最短距離

接下來的實現就只是比簡單的BFS多了一部分，難度不大，我們直接來實現一下代碼看看：

代碼實現：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
char a[N][N];
int dist[N][N];
int n, m;
typedef pair<int, int> PII;//存放坐標
//用于移動
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs()
{memset(dist, -1, sizeof(dist));//初始化dist數組為-1，避免出現歧義queue<PII> q;//多源BFSfor (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[i][j] == '1'){q.push({i, j});dist[i][j] = 0;}}}while(q.size()){PII t = q.front(); q.pop();int i = t.first, j = t.second;for (int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if (x < 1 || x > n || y < 1 || y > m) continue;//超出矩陣，直接跳過if (a[x][y] == '1') continue;//是1不是0也跳過if (dist[x][y] != -1) continue;//被填過最短距離，就跳過dist[x][y] = dist[i][j] + 1;//更新最短距離q.push({x, y});}}}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}bfs();for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << dist[i][j] << " ";}cout << endl;}return 0;
}

總結

在多源BFS中，只是多了將初始化的時候，多放入了許多起點。

大體思路實現都是不會有太大的變化。

希望大家能夠有所收獲，多多點贊 + 收藏 + 關注！