多源BFS的模板以及练习题（多源BFS）
模板
先看模板题吧
矩阵距离
给定一个 N 行 M 列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(i,j,k,l)=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(i,j,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的最小距离，那么母题在这里
洛谷P1443 马的遍历（bfs广搜的基本应用）-CSDN博客
这道题就是把母题中的“马”换成了可以上下左右移动的“兵”（题目当中的1），那么就相当于是多个起点，那区别就是初始化的时候要把这些点全部加入队列当中
代码：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
char str[N][N];
int dist[N][N];
int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int n,m;
void bfs()
{
memset(dist,-1,sizeof(dist));
queue<pair<int,int>> q;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
if(str[i][j] == '1'){
dist[i][j] = 0;
q.push(make_pair(i,j));
}
}
}
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i = 0;i < 4;i ++){
int nx = x + d[i][0],ny = y + d[i][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0;i < n;i ++) cin >> str[i];
bfs();
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}练习题
题目描述
众所周知，出题人没玩过双人成行，所以出了这道题
你一觉醒来，发现你和另一个时空的你被困在 n∗m大小矩形孤岛的 (x,y) 地块上
在地图中最多包含 平地，陷阱和传送门 三种不同地块
你和另外一个时空的你都可以上下左右移动到相邻的地块中
可是你和外一个时空的你只能同时以相反的方向移动
两人均不能跨过边界，即到达孤岛外的地方；任意人到达陷阱处会立刻死亡
现在，你能否给出一个移动序列，使得两人均能从传送门离开，其中任意一人到达传送门后一定会离开且不会再回到该孤岛中;
如果有，请输出该序列的最短长度、反之输出 -1
输入描述:
第一行四个正整数 n,m,x,y
接下来 n 行，每行一个长度为 m 的字符串
1≤n,m≤2×10^3; 1≤x≤n; 1≤y≤m
数据保证
字符串仅包含 .#@ 三种字符 .(平地) #(陷阱) @(传送门)
保证 (x,y)位置是平地.
输出描述:
输出一个整数
若能离开，请请输出该序列的最短长度
反之输出 -1
示例1
输入
复制3 3 2 2 @.@ #.. @.@
3 3 2 2 @.@ #.. @.@
输出
复制2
2
说明
你可以先往上后往左到达(1,1)传送门
另外一个时空的你会先下后右到达(3,3)传送门
示例2
输入
复制1 3 1 2 ..@
1 3 1 2 ..@
输出
复制3
3
示例3
输入
复制3 1 2 1 # . @
3 1 2 1 # . @
输出
复制-1
-1
说明
显然，谁都不想走到陷阱那 ...
备注:
本题输入较大，建议使用较快语言和较快的输入
在我看来，如果这道题对多源bfs没有很好的理解或者说没有一定的题量，会很懵逼，你想的到这是搜索，但你不知道怎么搜索，越想越懵
那么这道题的做法是：首先初始化好一个dist[N][N]数组，代表每个点到'@'的最短距离（其实这里一开始的时候还是不好想的），然后用s[N][N][2]定义两个状态‘0’：代表正常移动。'1':代表相反方向移动。从起点去bfs广搜（两个状态'0'、'1'），如果一个状态走到了'@'那么更新ans，ans = max(s[x1][y1][0] + dist[x2][y2])，另一个也一样，其实这里还是比较巧妙的，前提就是能想到多源bfs
代码
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
char str[N][N];
int dist[N][N];
int s[N][N][2];
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n,m,x,y;
int ans = 0x3f3f3f3f;
void bfs()
{
memset(dist,-1,sizeof(dist));
queue<pair<int,int>> q;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if(str[i][j] == '@'){
dist[i][j] = 0;
q.push(make_pair(i,j));
}
}
}
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int i = 0;i < 4;i ++){
int nx = x + d[i][0],ny = y + d[i][1];
if(nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != -1 || str[nx][ny] == '#') continue;
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
memset(s,-1,sizeof(s));
queue<tuple<int,int,int>> p;
s[x][y][0] = s[x][y][1] = 0;
p.push({x,y,0});
p.push({x,y,1});
while(!p.empty()){
auto [x1,y1,z1] = p.front();
p.pop();
auto [x2,y2,z2] = p.front();
p.pop();
if(str[x1][y1] == '@') ans = min(ans,s[x1][y1][0] + dist[x2][y2]);
if(str[x2][y2] == '@') ans = min(ans,s[x2][y2][1] + dist[x1][y1]);
for(int i = 0;i < 4;i ++){
int nx = x1 + d[i][0],ny = y1 + d[i][1];
if(nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny][0] != -1 || str[nx][ny] == '#') continue;
int nu = x2 - d[i][0],nv = y2 - d[i][1];
if(nu < 1 || nu > n || nv < 1 || nv > m || s[nu][nv][1] != -1 || str[nu][nv] == '#') continue;
s[nx][ny][0] = s[x1][y1][0] + 1;
s[nu][nv][1] = s[x2][y2][1] + 1;
p.push({nx,ny,0});
p.push({nu,nv,1});
}
}
}
int main()
{
cin >> n >> m >> x >> y;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> str[i][j];
}
}
bfs();
// for(int i = 1;i <= n;i ++){
// for(int j = 1;j <= m;j ++){
// cout << dist[i][j] << " ";
// }
// cout << endl;
// }
cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
return 0;
}加油