多源BFS
AcWing173. 矩阵距离
输入格式
第一行两个整数n,m。
接下来一个N行M列的01矩阵，数字之间没有空格。
输出格式
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。
数据范围
1 ≤ N , M ≤ 1000
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 1010; int n, m; int dist[N][N]; char g[N][N]; void bfs() { memset(dist, -1, sizeof dist); queue<PII>q; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (g[i][j] == '1') { q.push({ i,j }); dist[i][j] = 0; } } } int dx[4] = { 0,1,0,-1 }, dy[4] = { 1, 0, -1, 0 }; while (q.size()) { auto t = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int a = t.first + dx[i]; int b = t.second + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m)continue; if (dist[a][b] != -1)continue; dist[a][b] = dist[t.first][t.second] + 1; q.push({ 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]); } puts(""); } return 0; }
最小步数模型
AcWing1107. 魔板
Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。
这是一张有 8 个大小相同的格子的魔板：
1 2 3 4 8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这 8 种颜色用前 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 个整数，用空格分开，表示目标状态。
输出格式
输出文件的第一行包括一个整数，表示最短操作序列的长度。
如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; char g[2][4]; unordered_map<string, int> dist; unordered_map<string, pair<char, string>>pre; void set_(string state) { for (int i = 0; i < 4; ++i) { g[0][i] = state[i]; } for (int i = 3, j = 4; i >= 0; --i, ++j) { g[1][i] = state[j]; } } string get_() { string res; for (int i = 0; i < 4; ++i) { res += g[0][i]; } for (int i = 3; i >= 0; --i) { res += g[1][i]; } return res; } string move0(string state) { set_(state); for (int i = 0; i < 4; ++i)swap(g[0][i], g[1][i]); return get_(); } string move1(string state) { set_(state); char t[2]; t[0] = g[0][3]; t[1] = g[1][3]; for (int i = 3; i >= 0; --i) { for (int j = 0; j < 2; ++j) { g[j][i] = g[j][i - 1]; } } g[0][0] = t[0]; g[1][0] = t[1]; return get_(); } string move2(string state){ set_(state); char t = g[0][1]; g[0][1] = g[1][1]; g[1][1] = g[1][2]; g[1][2] = g[0][2]; g[0][2] = t; return get_(); } void bfs(string start, string end) { queue<string>q; q.push(start); if (start == end)return; while (q.size()) { auto t = q.front(); q.pop(); string m[3]; m[0] = move0(t); m[1] = move1(t); m[2] = move2(t); for (int i = 0; i < 3; ++i) { string str = m[i]; if (dist.count(str) == 0) { dist[str] = dist[t] + 1; pre[str].first = char(i + 'A'); pre[str].second = t; if (str == end)return; q.push(str); } } } } int main() { string end, start; for (int i = 0; i < 8; ++i) { int c; cin >> c; end += char(c + '0'); } for (int i = 0; i < 8; ++i) { start += char(i + '1'); } bfs(start, end); cout << dist[end] << endl; string res; while (end != start) { res += pre[end].first; end = pre[end].second; } reverse(res.begin(), res.end()); if (res.size())cout << res << endl; return 0; }
双端队列广搜(0-1 BFS)
适用于边权只有0和1的图
AcWing175. 电路维修
思路
只能通过偶点(横纵坐标和为偶数的点)
达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个R行C列的网格（R,C≤500），如下图所示。
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
注意：只能走斜向的线段，水平和竖直线段不能走。
输入格式
输入文件包含多组测试数据。
第一行包含一个整数T，表示测试数据的数目。
对于每组测试数据，第一行包含正整数R和C，表示电路板的行数和列数。
之后R行，每行C个字符，字符是"/"和"\"中的一个，表示标准件的方向。
输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。
数据范围
1 ≤ R , C ≤ 500
1 ≤ T ≤ 5
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, PII>PIII; const int N = 510; int n, m; PII p[N]; char g[N][N]; int dist[N][N]; bool vis[N][N]; int bfs() { memset(dist, 0x3f, sizeof dist); memset(vis, 0, sizeof vis); deque<PII>q; dist[0][0] = 0; q.push_back({ 0,0 }); while (q.size()) { auto t = q.front(); q.pop_front(); int x = t.first, y = t.second; if (x == n && y == m)return dist[x][y]; //找到终点直接返回 vis[x][y] = true; int dx[4] = { -1,-1,1,1 }, dy[4] = { -1,1,1,-1 }; //枚举四个方向 int ix[] = { -1,-1,0,0 }, iy[] = { -1,0,0,-1 }; //线路于当前点的相对位置 char ok[5] = "\\/\\/"; //不用移动的电路状态 for (int i = 0; i < 4; ++i) {// 遍历四个方向 int a = x + dx[i]; int b = y + dy[i]; if (a < 0 || a > n || b < 0 || b > m)continue; if (vis[a][b])continue; int ga = x + ix[i], gb = y + iy[i]; //找到电线在图中的位置 int w = g[ga][gb] != ok[i]; //将当前电线与当前点接通的花费 int d = dist[x][y] + w; //从队头转移到当前点的花费 if (d <= dist[a][b]) { //如果小于等于 则更新 dist[a][b] = d; if (!w)q.push_front({ a,b }); //边权为0 插入队头 else q.push_back({ a,b }); //边权为1 插入队尾 } } } return -1; } int main() { int t; cin >> t; while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i)scanf("%s", g[i]); if (n + m & 1)puts("NO SOLUTION"); else printf("%d\n", bfs()); } return 0; }
