思路分析
这道题是一道非常典型的 BFS 题目， BFS 所面临的最大问题是判断重复。显然，如果每次判断重复都扫描一次队列，搜索的效率会非常低，会提高一个指数级，所以一般宽度搜索的判断重复都是运用数组来实现的。那么数组下标就需要用一个 Hash 函数来计算。因此，设计 Hash 函数就显得非常重要。
本题 Hash 函数的设计：我们很容易想到将 8 个数字按顺时针顺序组合成 8 进制（每个数字都减 1 ）的 8 位基数。但是，这里最大的八进制数 76543210 ，转换成十进制数就是 16434824 ，也就是说要开大小为 16434824 的数组，如果题目强制空间限制，那么，数组下标会越界。
这里我们引入康托展开，即将一个排列对应成它在全排列中的序数，这样就不会 MLE 了。
如 {1,2,3,4,···,n } 表示 1,2,3,4,···,n 的一个排列，如 {1,2,3} 按从小到大排序，一共有6个： 1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1，分别代表数字 1,2,3,4,5,6，也就是把 10 进制数与一个排列对应起来。它们之间的对应关系可有康托展开来找到。如果想知道 321 时 {1,2,3} 中第几大的数，可以这样考虑：第一位是 3 ，当第一位的数字小于 3 时，对应的排列数都小于 321，如 123,213，则小于 3 的数有 1,2，所以有 2×2! 个；再看小于第二位的数 2 ，小于 2 的数只有一个就是 1，所以有 1×1!=1。因此小于 321 的 {1,2,3} 排列数共有 2×2!+1×1!=5 个，所以 321 是第六大的数。
再如 1324 是 {1,2,3,4} 排列数中第几大的数？ 第一位数字是 1，小于 1 的数没有，是 0 个，即 0×3! ；第二位数字是 3，小于 3 的数有 1,2，但 1 已经在第一位上，所以只有一个数 2，即 1×2! ；第三位数字是 2，小于 2 的数字是1 ，但是 1 在第一位上，所以有 0 个数，即 0×1! 。因此比 1234 小的排列有 0×3!+1×2!+0×1!=2个，所以 1324 是第三大的数。
设 step[] 记步数；记 i 的父节点为 prt[i];a[i] 表示第 i 个序列采用哪种变换。
附上详细代码及解释
#include <bits/stdc++.h>
using namespace std;
int jc[10] = { 1, 1, 2, 6, 24, 120, 720, 5040 };//jc[i]=i!
int g, st, prt[50005], b[1000000] = { 0 }, step[50005];
char a[50005];
struct mb { int a[2][4]; } start, goal, q[90000];
int Turn(mb x)//康托展开
{
int i, j, res = 0, t[8], s;
for (i = 0; i < 4; i++) t[i] = x.a[0][i]; //构成序列
for (i = 3; i >= 0; i--) t[7 - i] = x.a[1][i];
for (i = 0; i < 8; i++) {
s = 0;
for (j = i + 1; j <= 7; j++) if (t[j] < t[i]) s++; //找到后面小于t[i]的值
res += jc[7 - i] * s;
}
return res;
}
mb Change(int way, int num)//三种基本操作
{
mb temp;
if (way == 1) {//A
for (int i = 0; i < 4; i++) temp.a[0][i] = q[num].a[1][i];
for (int i = 0; i < 4; i++) temp.a[1][i] = q[num].a[0][i];
return temp;
}
if (way == 2) {//B
temp.a[0][0] = q[num].a[0][3];
temp.a[1][0] = q[num].a[1][3];
for (int i = 1; i < 4; i++) temp.a[0][i] = q[num].a[0][i - 1];
for (int i = 1; i < 4; i++) temp.a[1][i] = q[num].a[1][i - 1];
return temp;
}
if (way == 3) {//C
temp.a[0][0] = q[num].a[0][0]; temp.a[0][3] = q[num].a[0][3];
temp.a[1][0] = q[num].a[1][0]; temp.a[1][3] = q[num].a[1][3];
temp.a[0][1] = q[num].a[1][1]; temp.a[0][2] = q[num].a[0][1];
temp.a[1][2] = q[num].a[0][2]; temp.a[1][1] = q[num].a[1][2];
return temp;
}
}
void Print(int num)//递归输出结果
{
if (num == 1) return;
Print(prt[num]);
cout << a[num];
}
void Bfs()
{
int op = 1, cl = 1, i, t;
mb temp;
q[1] = start;
step[1] = 0; prt[1] = 1;
while (op <= cl) {
for (i = 1; i <= 3; i++) { //三种变换
temp = Change(i, op);
t = Turn(temp); //计算对应序号
if (!b[t]) {
q[++cl] = temp;
step[cl] = step[op] + 1;
b[t] = 1; //标记
prt[cl] = op; //prt[cl]:记录cl的父节点为prt[cl]
a[cl] = char('A' + i - 1); //a[cl]：表示第cl个序列采用哪种变换
if (t == g) {
cout << step[cl] << endl; Print(cl); return;
}
}
}
op++;
}
}
signed main()
{
int i;
for (i = 0; i < 4; i++) start.a[0][i] = i + 1; //初始化起始状态
for (i = 3; i >= 0; i--) start.a[1][i] = 8 - i;
st = Turn(start); b[st] = 1; //标记起始状态
for (i = 0; i < 4; i++) cin >> goal.a[0][i]; //读入目标状态
for (i = 3; i >= 0; i--) cin >> goal.a[1][i];
g = Turn(goal); //计算目标状态的值
if (g == st) {
cout << 0; return 0;
} //注意：起始状态和目标状态相同
Bfs();
return 0;
}