思路分析

这道题是一道非常典型的 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;
}