BFS中的多源BFS、最小步数模型和双端队列广搜
多源BFS
多源BFS时有从多个源点出发的bfs算法,只需要将多个源点都连一条边权为0的边到虚拟源点,那么问题就等价于从虚拟源点开始BFS。
一开始直接将所有源点加入BFS的队列即可.
173. 矩阵距离
给定一个 N N N 行 M M M 列的 01 01 01 矩阵 A A A， A [ i ] [ j ] A[i][j] A[i][j][j] 与 A [ k ] [ l ] A[k][l] A[k][l] 之间的曼哈顿距离定义为： d i s t ( i , j , k , l ) = ∣ i − k ∣ + ∣ j − l ∣ dist(i,j,k,l)=|i−k|+|j−l| dist(i,j,k,l)=∣i−k∣+∣j−l∣
输出一个 N N N 行 M M M 列的整数矩阵 B B B，其中： B [ i ] [ j ] = m i n 1 ≤ x ≤ N , 1 ≤ y ≤ M , A [ x ] [ y ] = 1 d i s t ( i , j , x , y ) B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}dist(i,j,x,y) B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(i,j,x,y)
输入格式
第一行两个整数 N , M N,M N,M。
接下来一个 N N N 行 M M M 列的 01 01 01 矩阵，数字之间没有空格。
输出格式
一个 N N N 行 M M M 列的矩阵 B B B，相邻两个整数之间用一个空格隔开。
数据范围
1 ≤ N , M ≤ 1000 1≤N,M≤1000 1≤N,M≤1000
输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1
思路：
- 本题目的意思就是求出所有点到 1 1 1 的最短距离
- 首先将所有的点 1 1 1 坐标放入队列中，进行多源 BFS
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n, m, dist[N][N], dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
char g[N][N];
bool st[N][N];
queue<PII> q;
void bfs(){
while(q.size()){
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int i = 1; i <= 4; i++){
int tx = x + dx[i], ty = y + dy[i];
if(tx < 0 || tx >= n || ty < 0 || ty >= m || st[tx][ty]) continue;
dist[tx][ty] = dist[x][y] + 1;
q.push({tx, ty});
st[tx][ty] = true;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if(j) cout << " " << dist[i][j];
else cout << dist[i][j];
}
cout << endl;
}
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> g[i];
for (int j = 0; j < m; j++){
if(g[i][j] == '1'){
q.push({i, j});
st[i][j] = true;
}
}
}
bfs();
return 0;
}
最小步数模型
1107. 魔板
Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。
这是一张有 8 8 8 个大小相同的格子的魔板：
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这 8 8 8 种颜色用前 8 8 8 个正整数来表示。
可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。
对于上图的魔板状态，我们用序列 ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ) (1,2,3,4,5,6,7,8) (1,2,3,4,5,6,7,8) 来表示，这是基本状态。
这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：
A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范：
A：
8 7 6 5
1 2 3 4
B：
4 1 2 3
5 8 7 6
C：
1 7 2 4
8 6 3 5
对于每种可能的状态，这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。
注意：数据保证一定有解。
输入格式
输入仅一行，包括 8 8 8 个整数，用空格分开，表示目标状态。
输出格式
输出文件的第一行包括一个整数，表示最短操作序列的长度。
如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为 1 1 1 到 8 8 8 之间的整数。
输入样例：
2 6 8 4 5 7 3 1
输出样例：
7
BCABCCB
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<string, string> PII;
string source = "12345678", target;
string move1(string s){
reverse(s.begin(), s.end());
return s;
}
string move2(string s){
return s[3] + s.substr(0, 3) + s.substr(5, 3) + s[4];
}
string move3(string s){
swap(s[1], s[2]);
swap(s[5], s[6]);
swap(s[1], s[5]);
return s;
}
void bfs(){
map<string, int> mp;
queue<PII> q;
q.push({source, ""});
mp[source] = 1;
while(q.size()){
auto t = q.front();
q.pop();
string state = t.first, step = t.second;
if(state == target){
cout << step.length() << endl;
if(step.length()) cout << step << endl;
return ;
}
string tstate = move1(state);
if(!mp[tstate]){
q.push({tstate, step + "A"});
mp[tstate] = 1;
}
tstate = move2(state);
if(!mp[tstate]){
q.push({tstate, step + "B"});
mp[tstate] = 1;
}
tstate = move3(state);
if(!mp[tstate]){
q.push({tstate, step + "C"});
mp[tstate] = 1;
}
}
}
int main(){
for (int i = 1; i <= 8; i++){
string n;
cin >> n;
target = target + n;
}
bfs();
return 0;
}
双端队列广搜
双端队列广搜主要解决图中边的权值只有0或者1的最短路问题，注意和多源BFS不一样，这种是无法用连虚拟源点那种做法的。
双端队列广搜中，边权为0的点放到队头，边权为1的点放到队尾，这样队列仍然满足单调性，且形式上和普通广搜一样，前面的点和后面的点距离相差为1。
普通bfs判断终点，在入队就时就能算出最小距离，双端队列广搜必须在出队时才知道点的最小值。因为有可能终点入队是被距离为1的边入的，后面的点可能会搜到离终点距离为0的边让其入队，故入队时不一定是最小距离，但出队时一定是。
**操作：**每次从队头取出元素，并进行拓展其他元素时
- 若拓展某一元素的边权是 0 0 0，则将该元素插入到队头
- 若拓展某一元素的边权是 1 1 1，则将该元素插入到队尾
与堆优化Dijkstra 一样，必须在出队时才知道每个点最终的最小值，而和一般的bfs不一样，原因是如下图所示
175. 电路维修
达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个 R R R 行 C C C 列的网格（ R , C ≤ 500 R,C≤500 R,C≤500），如下图所示。
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
注意：只能走斜向的线段，水平和竖直线段不能走。
输入格式
输入文件包含多组测试数据。
第一行包含一个整数 T T T，表示测试数据的数目。
对于每组测试数据，第一行包含正整数 R R R 和 C C C，表示电路板的行数和列数。
之后
R
R
R 行，每行
C
C
C 个字符，字符是"/"和"\"中的一个，表示标准件的方向。
输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。
数据范围
1
≤
R
,
C
≤
500
1≤R,C≤500
1≤R,C≤500,
1
≤
T
≤
5
1≤T≤5
1≤T≤5
输入样例：
1
3 5
\\/\\
\\///
/\\\\
输出样例：
1
样例解释
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
思路：
-
首先明确的一点是，这里是图中的格子和点是不一样的，点是格子上的角角上的点，每个点都有4个方向可以走，分别对应的是左上角，右上角，右下角，左下角
-
踩过格子到达想去的点时，需要判断是否需要旋转电线，若旋转电线表示从 当前点 到 想去的点 的边权是 1 1 1，若不旋转电线则边权是 0 0 0
-
按左上角，右上角，右下角，左下角遍历的顺序
dx[]和dy[]表示可以去其他点的方向id[]和iy[]表示需要踩某个方向的各种才能去到相应的点cs[]表示当前点走到 4 4 4 个方向的点理想状态下格子形状(边权是 0 0 0 的状态)
#include<iostream>
#include<deque>
#include<cstring>
using namespace std;
const int N = 510;
typedef pair<int,int> PII;
int t, n, m, dist[N][N];
char g[N][N];
bool st[N][N];
void bfs(){
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1}, ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
char s[5] = "\\/\\/";
deque<PII> q;
q.push_back({0, 0});
dist[0][0] = 0;
while(q.size()){
auto t = q.front();
q.pop_front();
int x = t.first, y = t.second;
if(x == n && y == m){
cout << dist[x][y] << endl;
return;
}
if(st[x][y]) continue;
for (int i = 0; i < 4; i++){
int tx = x + dx[i], ty = y + dy[i];
if(tx < 0 || tx > n || ty < 0 || ty > m) continue;
int xx = x + ix[i], yy = y + iy[i];
int w = (g[xx][yy] != s[i]);
if(dist[tx][ty] > dist[x][y] + w){
dist[tx][ty] = dist[x][y] + w;
if(w) q.push_back({tx, ty});
else q.push_front({tx, ty});
}
}
}
}
int main(){
cin >> t;
while(t--){
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
if(n + m & 1) puts("NO SOLUTION");
else bfs();
}
return 0;
}