c++最小步数模型（魔板）
C++ 最小步数模型通常用于寻找两个点之间的最短路径或最少步数。以下是一个基本的 C++ 最小步数模型的示例代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
int d[N];
bool vis[N];void bfs(int s) {queue<int> que;que.push(s);vis[s] = true;while (!que.empty()) {int x = que.front();que.pop();for (auto y : G[x]) {if (!vis[y]) {que.push(y);vis[y] = true;d[y] = d[x] + 1;}}}
}int main() {int n, m;cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;G[x].push_back(y);G[y].push_back(x);}bfs(1);cout << d[n] << endl;return 0;
}
在这个例子中，我们使用了广度优先搜索算法（BFS）来遍历整个图，并计算每个点到起点的最短距离。具体地，我们将起点加入队列中，并在之后的每个循环中依次访问队列中的每个点。对于每个访问过的点，我们遍历与其相邻的所有节点，并在遇到未访问过的节点时将其加入队列，并更新其距离，即 d[y] = d[x] + 1。最后，我们输出终点 n 到起点的最短距离 d[n]。
注意，我们还需要使用一个数组 vis 来记录每个节点是否已经被访问过。在每次遍历时，我们需要先检查当前节点是否已经被访问过，如果访问过则跳过，否则将其标记为已访问，并处理其相邻节点。
先看题目：
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 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先看代码
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>using namespace std;unordered_map<string, pair<string, char>> pre; // pre存的是当前状态所对应的上一状态的状态和操作inline string operA(string str)
{for (int i = 0; i < 4; ++ i) swap(str[i], str[7 - i]);return str;
}inline string operB(string str)
{for (int i = 0; i < 3; ++ i) swap(str[2 - i], str[3 - i]), swap(str[4 + i], str[5 + i]);return str;
}inline string operC(string str)
{swap(str[1], str[2]), swap(str[5], str[6]), swap(str[1], str[5]);return str;
}void bfs(string start, string end)
{queue<string> que;que.push(start); // 必须从start向end搜索才能保证字典序最小while (!que.empty()) {string str = que.front();que.pop();if (str == end) return;string move[3]; // 记录下该状态可由三种操作所达到的新状态move[0] = operA(str), move[1] = operB(str), move[2] = operC(str);for (int i = 0; i < 3; ++ i) // 遍历三种状态{ if (!pre.count(move[i])) // 如果当前状态还没有被记录过{ que.push(move[i]); // 将当前状态入队pre[move[i]] = make_pair(str, 'A' + i); // 存下当前状态所对应的上一状态的状态和操作}}}
}signed main()
{int x;string start = "12345678", end, res;for (int i = 0; i < 8; ++ i) {scanf("%d", &x);end += char(x + '0');}bfs(start, end);while (end != start) { // 从最终状态向起始状态回溯res = pre[end].second + res; // 注意要把前一个操作放在输出序的前面end = pre[end].first;}if (res.length() == 0) printf("0");else printf("%d\n%s", res.length(), res.c_str());return 0;
}