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 4

B:

4 1 2 3
5 8 7 6

C:

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;
}