多源BFS
多源BFS时有从多个源点出发的bfs算法,只需要将多个源点都连一条边权为0的边到虚拟源点,那么问题就等价于从虚拟源点开始BFS。
一开始直接将所有源点加入BFS的队列即可.
矩阵距离
输入样例：
3 4 0001 0011 0110输出样例：
3 2 1 0 2 1 0 0 1 0 0 1
思路
题意为搜索所有0点到一群1点的最短曼哈顿距离。
将所有为1的点直接加入bfs队列，向外搜索，由bfs性质到达的点一定离虚拟源点最短,而到虚拟源点的距离 == 到1点的距离,故最短。
代码
/*
* @Author: ACCXavier
* @Date: 2022-01-22 19:24:15
* @LastEditTime: 2022-01-22 20:53:50
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/activity/content/problem/content/1474/
* @keywords: 多源BFS
* 将所有的0看成起点，所有0连一条权为0的边到一个虚拟源点，就是在求其他所有点到虚拟源点的最短路。
* 直接将这些0点加入BFS队列即可，让他们继续外扩，由bfs的性质到达一定最短
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n,m;
char g[N][N];
int dist[N][N];
PII q[N * N];
void bfs(){
int hh = 0,tt = -1;
memset(dist,-1,sizeof dist);
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
if(g[i][j] == '1'){// '1'
dist[i][j] = 0;
q[++ tt] = {i,j};
}
}
}
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(){
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]);
}
printf("\n");
}
}
最小步数模型
BFS可以求各种广义最短路。直接看例题
魔板
Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。
这是一张有 88 个大小相同的格子的魔板：
1 2 3 4 8 7 6 5我们知道魔板的每一个方格都有一种颜色。
这 88 种颜色用前 88 个正整数来表示。
可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。
对于上图的魔板状态，我们用序列 (1,2,3,4,5,6,7,8)来表示，这是基本状态。
这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：
A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。下面是对基本状态进行操作的示范：
A：
8 7 6 5 1 2 3 4B：
4 1 2 3 5 8 7 6C：
1 7 2 4 8 6 3 5对于每种可能的状态，这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。
注意：数据保证一定有解。
输入格式
输入仅一行，包括 88 个整数，用空格分开，表示目标状态。
输出格式
输出文件的第一行包括一个整数，表示最短操作序列的长度。
如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为 11 到 88 之间的整数。
输入样例：
2 6 8 4 5 7 3 1输出样例：
7 BCABCCB
思路
用数组存输入数据，操作手推一下就行了。
每做一次变换就算一步，在bfs每轮中进行三种操作。为了满足最小字典序要按A,B,C的顺序操作,操作后的状态如果没有访问过则进入队列，记录。
注意答案要操作顺序，所以要记录每个操作的上一步操作，最后逆向输出即可。
如果学过群论，那么可以知道本题的三种置换在魔板上构成S8的子群(结合律,逆元,单位元,有限性)
代码
/*
* @Author: ACCXavier
* @Date: 2022-01-22 20:53:09
* @LastEditTime: 2022-01-22 21:48:31
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/activity/content/problem/content/1475/
* @keywords: BFS 最小步数模型
* 魔板的变换是8阶置换群的子群
* 板的状态是cayley图上的一点，寻找目标状态的最短路，允许的操作g有三种
* 在此之上BFS，注意记录每一步的变换方式
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6;
int g[2][4];
string start,tar;//@不要用end命名
unordered_map<string,int>dist;//到string状态用的步数
unordered_map<string,pair<char,string>>pre;// 变化到键的状态的操作是char存储，键状态的前一个状态是值里的string存贮
string q[N];//队列
string move0(string st){
string res = st;
reverse(res.begin(),res.end());
return res;
}
string move1(string t)
{
for(int i=0;i<3;i++) swap(t[3],t[i]);
for(int i=4;i<7;i++) swap(t[i],t[i+1]);
return t;
}
string move2(string st){
string res = st;
swap(st[1],st[6]);
swap(st[5],st[6]);
swap(st[2],st[5]);
return st;
}
int bfs(){
if(start == tar)return 0;
q[0] = start;
int hh = 0,tt = 0;
dist[start] = 0;
while(hh <= tt){
string t = q[hh ++];
string m[3];
m[0] = move0(t);
m[1] = move1(t);
m[2] = move2(t);
//按照ABC三种操作的顺序BFS正好能找到最小字典序
//因为bfs的过程就保证了是按最小字典序找的，A操作的后续必然先扩展，先加入队列，之后是B,C
//下面看的都是将要转移的状态
for(int i = 0; i < 3; ++ i){
if(!dist.count(m[i])){//状态没有被访问过
//!count(m[i])
dist[m[i]] = dist[t] + 1;
pre[m[i]] = {'A' + i,t};//m[i]由A + i操作转移过来
q[++ tt] = m[i];
if(m[i] == tar) return dist[tar];
}
}
}
return -1;
}
int main()
{
for(int i = 0; i < 8; ++ i){
int t;cin >> t;
tar += char(t + '0');//+ '0'
}
start = "12345678";
int step = bfs();
cout << step << endl;
string res;
while(tar != start){
res += pre[tar].first;//取操作（逆序）
tar = pre[tar].second;//变上一个状态
}
reverse(res.begin(),res.end());
if(step > 0)cout << res << endl;
return 0;
}
双端队列广搜
双端队列广搜主要解决图中边的权值只有0或者1的最短路问题，注意和多源BFS不一样，这种是无法用连虚拟源点那种做法的。
双端队列广搜中，边权为0的点放到队头，边权为1的点放到队尾，这样队列仍然满足单调性，且形式上和普通广搜一样，前面的点和后面的点距离相差为1。
普通bfs判断终点，在入队就时就能算出最小距离，双端队列广搜必须在出队时才知道点的最小值。因为有可能终点入队是被距离为1的边入的，后面的点可能会搜到离终点距离为0的边让其入队，故入队时不一定是最小距离，但出队时一定是。
电路维修
达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个 R 行 C 列的网格（R,C≤500），如下图所示。
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
注意：只能走斜向的线段，水平和竖直线段不能走。
输入格式
输入文件包含多组测试数据。
第一行包含一个整数 T，表示测试数据的数目。
对于每组测试数据，第一行包含正整数 R 和 C，表示电路板的行数和列数。
之后 R 行，每行 C 个字符，字符是
"/"和"\"中的一个，表示标准件的方向。输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出
NO SOLUTION。数据范围
1≤R,C≤500
1≤T≤5输入样例：
1 3 5 \\/\\ \\/// /\\\\输出样例：
1样例解释
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
思路
找到最少的开关让电路联通的问题，我们设开关动一次算边权为1，不动算边权为0，则问题等价于找到一条最短路。
图中给出格子和我们的图之间需要换算，因为路的节点是在格点上，而路（开关）在格子中。具体关系为
dx，dy用于到达点的方向遍历，ix，iy用于到点所用的边（开关）的方向遍历。
另外，开关每次让横纵坐标之和变化偶数，故从（0，0）点只能到达横纵坐标之和为偶数的点，故当n+m为奇可直接排除。
还有一些细节见代码注释。
代码
/*
* @Author: 爱学习的图灵机
* @Date: 2022-01-23 11:58:20
* @LastEditTime: 2022-01-31 22:58:28
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/activity/content/problem/content/1476/
* @keywords: 双向BFS
* 要转的电路边权为1，不转的为0，寻找开关旋转次数转换为最短路问题（最短路不会有回路，开关也不会旋转两次）
* 带0和1的最短路用双端队列bfs，搜到为0的点插入队头
* 开关每次让横纵坐标之和变化偶数，故从（0，0）点只能到达横纵坐标之和为偶数的点，n+m为奇可直接排除
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 510,M = N * N;
int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int bfs(){
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
dist[0][0] = 0;
deque<PII> q;//双端队列
q.push_back({0,0});
char cs[] = "\\/\\/";//\需要转义字符\。当前点走到4个方向的点理想状态下格子形状(边权是0的状态)
int dx[4] = {-1,-1,1,1};dy[4] = {-1,1,1,-1};//方向
int ix[4] = {-1,-1,0,0};iy[4] = {-1,0,0,-1};//格点相对于中心点的偏移
//https://cdn.acwing.com/media/article/image/2020/10/02/7416_260b418204-8f4c96e579549999453c9467edbbe41.png
while(q.size()){
PII t = q.front();
q.pop_front();
if(st[t.x][t.y])continue;
st[t.x][t.y] = true;
//@ 要访问四个方向的开关，而是不是交点（线上的点）。每个交点能够被四个开关找到，也就是可以被不重复访问四次。（a，b）是交点的位置，所以在循环中st[a][b]不能拿来判重,（ca，cb)是开关的位置，所以st[ca][cb]可以拿来判重。这里直接在入队时看交点有没有被“访问过”，交点被“访问过”是指四个方向的开关都看过了，
//距离严格变小才能进入队列，因此之前走过的点不会进入再次队列中
//看交点的四个开关
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;
int ca = t.x + ix[i],cb = t.y + iy[i];//开关的位置
/*
if(st[ca][cb])continue;
st[ca][cb] = true;
*/
int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);//不同则需要翻转，+1
if(dist[a][b] > d){
dist[a][b] = d;
if(g[ca][cb] != cs[i])q.push_back({a,b});
else q.push_front({a,b})//插入队头
}
}
}
return dist[n][m];
}
int main(){
int T;
scanf("%d",&T);
while(T --){
scanf("%d%d",&n,&m);
for(int i = 0; i < n; ++ i)scanf("%s",g[i]);
int t = bfs();
if(t == 0x3f3f3f3f)puts("NO SOLUTION");
else printf("%d\n",t);
}
return 0;
}
双向广搜
单向广搜随着步数增多搜索点数呈指数级增加，双向在一般情况下能够降低数量级，视图如下：
双向BFS每次必须搜一层，如果每次只搜一个，可能会出现如下情况：
两个方向都搜了一个，搜到就确认是最小值，但实际上可能存在更优的虚线路径。
字串变换
已知有两个字串 AA, BB 及一组字串变换的规则（至多 66 个规则）:
A1→B1A1→B1
A2→B2A2→B2
…
规则的含义为：在 AA 中的子串 A1A1 可以变换为 B1B1、A2A2 可以变换为 B2…B2…。
例如：AA＝
abcdBB＝xyz变换规则为：
abc` →→ `xu` `ud` →→ `y` `y` →→ `yz则此时，AA 可以经过一系列的变换变为 BB，其变换的过程为：
abcd` →→ `xud` →→ `xy` →→ `xyz共进行了三次变换，使得 AA 变换为 BB。
输入格式
输入格式如下：
AA BB
A1A1 B1B1
A2A2 B2B2
… …第一行是两个给定的字符串 AA 和 BB。
接下来若干行，每行描述一组字串变换的规则。
所有字符串长度的上限为 2020。
输出格式
若在 1010 步（包含 1010 步）以内能将 AA 变换为 BB ，则输出最少的变换步数；否则输出
NO ANSWER!。输入样例：
abcd xyz abc xu ud y y yz输出样例：
3
思路
从A串向B搜索，也从B向A搜索，共用搜索规则。
搜索时有个trick，每次搜队列中元素少的，也就是先搜分至少的方向。能让两端的搜索树更均衡。
替换使用substr函数，substr的第二个参数是长度不是位置，不填表示取后面的全部。
代码
/*
* @Author: ACCXavier
* @Date: 2022-01-24 11:44:04
* @LastEditTime: 2022-02-02 00:10:57
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/activity/content/problem/content/1477/
* @keywords: 双向BFS
* 从两个方向bfs，a向b搜索，b向a搜索，字串变换规则正好相反，体现在传参上
*/
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
string A,B;
string a[10],b[10];
int n;
//双向bfs每次必须扩展一层https://www.acwing.com/activity/content/code/content/132167/
int extend(queue<string>& q,unordered_map<string,int>& da,unordered_map<string,int>&db,string a[],string b[]){//!引用
int d = da[q.front()];
while(q.size() && da[q.front()] == d){//第一个判断保证有有点可搜索，第二个判断队首元素还在d这一层
auto t = q.front();
q.pop();
for(int i = 0; i < n; ++ i){//遍历n个规则
for(int j = 0; j < t.size(); ++ j){//枚举子串
if(t.substr(j,a[i].size()) == a[i])//相同可替换时
{
//!substr第二个参数是向后延伸的位数不是位置
string r = t.substr(0,j) + b[i] + t.substr(j + a[i].size());//substr加一个参数就是从参数到结尾
//最后不能用b[i].size()，因为t串中原来是a的长度
if(da.count(r))continue;//重复
if(db.count(r))return da[t] + db[r] + 1;//搜到相同位置，
da[r] = da[t] + 1;
q.push(r);
}
}
}
}
return 11;
}
int bfs()
{
if (A == B) return 0;//!
unordered_map<string,int> da,db;
queue<string>qa,qb;
qa.push(A);
qb.push(B);
da[A] = db[B] = 0;
int step = 0;
while(qa.size() && qb.size()){//如果有队列空了，说明某个方向的全搜完了都没到，无解
int t;
if(qa.size() < qb.size()){//每次挑分支少的搜一层
t = extend(qa,da,db,a,b);
}else{
t = extend(qb,db,da,b,a);
}
if(t <= 10)return t;
if(++ step == 10)return - 1;//先++再比较，第10次才会成立
}
return -1;
}
int main(){
cin >> A >> B;
while(cin >> a[n] >> b[n])n ++;
int step = bfs();
if(step == -1)puts("NO ANSWER!");
else printf("%d\n",step);
return 0;
}