多源BFS
一、簡介
多源BFS與單源BFS有什么區別呢？
- 單源BFS：從某一個點開始（起點）
- 多源BFS：從多個點同時開始走
如何解決多源BFS？
多源BFS：多個起點 ——> 多個起點同時加入佇列！
核心：在求解多源BFS問題時，同時將所有起點加入佇列即可！
二、練習
1.矩陣距離
【題目鏈接】173. 矩陣距離 - AcWing題庫
給定一個 NN 行 MM 列的 0101 矩陣 AA，A[i] [j] 與A[k] [l] 之間的曼哈頓距離定義為：
dist(A[i] [j],A[k] [l])=|i?k|+|j?l|
輸出一個 N 行 M 列的整數矩陣 B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])輸入格式
第一行兩個整數 N,M，
接下來一個 N 行 M 列的 01 矩陣，數字之間沒有空格，
輸出格式
一個 N 行 M 列的矩陣 B，相鄰兩個整數之間用一個空格隔開，
資料范圍
1≤N,M≤1000
輸入樣例：
3 4 0001 0011 0110輸出樣例：
3 2 1 0 2 1 0 0 1 0 0 1
思路：
- 將所有的1的點（起點）加入佇列
- 按照普通寬搜的方式，將其他未被搜過的點擴展出來，通過d[N] [N]陣列標志且維護距離，這樣就得到了每個點到所有1的最短距離！
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1010;
char g[N][N];
int d[N][N];//存放非1的點到所有1的點的最短距離
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
void bfs()
{
memset(d, -1, sizeof d);
//將所有起點加入佇列
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
{
if(g[i][j] == '1')
{
q.push({i, j});
d[i][j] = 0;//起點到自己的距離為0
}
}
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(d[a][b] != -1) continue;
q.push({a, b});//鄰接節點入隊
d[a][b] = d[t.first][t.second] + 1;//更新距離
}
}
}
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 ", d[i][j]);
puts("");
}
return 0;
}
2.擴散
【題目描述】
小藍在一張無限大的特殊畫布上作畫，
這張畫布可以看成一個方格圖，每個格子可以用一個二維的整數坐標表示，
小藍在畫布上首先點了一下幾個點：(0，0)，(2020，11)，(11，14)，(2000，2000)，只有這幾個格子上有黑色，其它位置都是白色的，
每過一分鐘，黑色就會擴散一點，具體的，如果一個格子里面是黑色，它就會擴散到上、下、左、右四個相鄰的格子中，使得這四個格子也變成黑色（如果原來就是黑色，則還是黑色），
請問，經過 2020 分鐘后，畫布上有多少個格子是黑色的，
本題無輸入，請直接輸出一個答案即可，
思路：
每分鐘擴散1點，說明了邊權都為1，而且有多個起點，因此可以使用多源BFS，維護一個d[i][j]陣列來記錄當前的點是第幾分鐘的，
多源BFS：將所有黑墨水加入佇列，然后寬搜染色或者統計可以被染色的白點的個數，若采用染黑的方法最后再遍歷地圖統計即可；若統計的是可以被染成黑色的白點個數，最后答案要加4（原來的4個黑點），
注：
由于沒有地圖給我們，我們先構建一張盡可能大的地圖
位置（0，0）若是向上下左右四個方向擴散的話就會出現負坐標的情況，如（0， -2020），但是陣列是沒有負數下標的，因此我們可以擴大初始坐標，如將原來的4個初始起點加上3000
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int maxn = 10000;
char g[maxn][maxn];
int d[maxn][maxn];//記錄距離
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int cnt;
void bfs()
{
memset(d, -1, sizeof d);
//所有起點加入佇列
q.push({3000, 3000});
q.push({5020, 3011});
q.push({3011, 3014});
q.push({5000, 5000});
//初始化距離
d[3000][3000] = d[5020][3011] = d[3011][3014] = d[5000][5000] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
if(d[t.first][t.second] == 2020) break ;// 2020分鐘后結束
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= maxn || b < 0 || b >= maxn) continue;
if(d[a][b] != -1 || g[a][b] == '#') continue;
//可以被染黑的節點入隊
q.push({a, b});
d[a][b] = d[t.first][t.second] + 1;
cnt ++;
}
}
}
int main()
{
//自己建圖
for (int i = 0; i < maxn; i ++ )
{
for(int j = 0; j < maxn; j ++)
g[i][j] = '.';
}
//四個起點標記為黑墨水
g[3000][3000] = g[5020][3011] = g[3011][3014] = g[5000][5000] = '#';
bfs();//統計可以被4個起點染黑的白點個數
cout << cnt + 4;//總的黑點個數：被染黑 加上 原來的4個黑點
return 0;
}
答案：20312088
三、總結
多源BFS的核心就是：將多個起點都加入佇列，然后再寬搜！
學習內容參考：
藍橋杯2020國賽真題
acwing演算法提高課
注：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/418115.html
標籤：其他
上一篇：SAE 最佳實踐范本：助力視野數科進入云原生“快車道”
下一篇：RabbitMQ 環境安裝