题目背景
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有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”：魔板中央四格作顺时针旋转。
下面是对基本状态进行操作的示范：
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个整数，用空格分开（这些整数在范围 1——8 之间）不换行，表示目标状态。
输出格式：
Line 1: 包括一个整数，表示最短操作序列的长度。
Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。
输入输出样例
2 6 8 4 5 7 3 1
7 BCABCCB
说明
题目翻译来自NOCOW。
USACO Training Section 3.2
分析：很显然，这是一道bfs的题目，难点就在于要怎么记录状态.因为题目给的是一个排列，所以很显然，可以用康托展开.具体的展开方式是这样的，考虑第i个数，在i后面有j个比i小的数，那么i的贡献值xi = j * (8 - i)!,∑xi (1 <= i <= n)就是当前排列的状态了.康托展开可以把排列变成一个数来保存，非常方便.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <queue> using namespace std; int vis[50010]; struct node { int a[9],zhuangtai,d; string print; }s,t; int jiecheng(int x) { int t = 1; for (int i = 2; i <= x; i++) t *= i; return t; } int kangtuo(node x) { int num = 0; for (int i = 1; i <= 8; i++) { int cnt = 0; for (int j = i + 1; j <= 8; j++) if (x.a[i] > x.a[j]) cnt++; num += cnt * jiecheng(8 - i); } return num; } node A(node x) { for (int i = 1; i <= 4; i++) swap(x.a[i],x.a[9 - i]); x.d++; return x; } node B(node x) { for (int i = 4; i >= 2; i--) { swap(x.a[i-1],x.a[i]); swap(x.a[9-i],x.a[10 - i]); } x.d++; return x; } node C(node x) { swap(x.a[3],x.a[2]); swap(x.a[7],x.a[6]); swap(x.a[2],x.a[6]); x.d++; return x; } void bfs() { queue <node> q; q.push(s); vis[s.zhuangtai] = 1; while (!q.empty()) { node u = q.front(); q.pop(); if (u.zhuangtai == t.zhuangtai) { printf("%d ",u.d); cout << u.print << endl; return; } for (int i = 1; i <= 3; i++) { node temp; if (i == 1) temp = A(u); if (i == 2) temp = B(u); if (i == 3) temp = C(u); temp.zhuangtai = kangtuo(temp); if (!vis[temp.zhuangtai]) { vis[temp.zhuangtai] = 1; if (i == 1) temp.print = u.print + 'A'; if (i == 2) temp.print = u.print + 'B'; if (i == 3) temp.print = u.print + 'C'; q.push(temp); } } } } int main() { for (int i = 1; i <= 8; i++) s.a[i] = i; s.zhuangtai = kangtuo(s); s.print = ""; s.d = 0; for (int i = 1; i <= 8; i++) scanf("%d",&t.a[i]); t.zhuangtai = kangtuo(t); t.print = ""; bfs(); return 0; }