题目描述

这是一张有 8 个大小相同的格子的魔板：

1 2 3 4
8 7 6 5

规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个一维序列。

对于上图的魔板状态，我们用序列 (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

你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。

输入格式
输入仅一行，包括 8 个整数，用空格分开，表示目标状态。

输出格式
输出文件的第一行包括一个整数，表示最短操作序列的长度。

如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。

数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。

样例

输入样例：

2 6 8 4 5 7 3 1

输出样例：

7
BCABCCB

本人发现y总的代码中间有一个比较费时的操作

就是将一维表示转变成二维，操作后再变回一维。。。

其实我们可以给题目所说的三种操作在一维表示中找三种代替操作。

操作A：

原操作：交换上下两行
被操作：12345678
操作后：87654321
代替操作：把一维表示整个倒过来

操作B：

原操作：将最右边的一列插入到最左边
被操作：12345678
操作后：41236785
代替操作：把第3位（从0开始）挪到最前面，把第4位挪到最后面

操作C：

原操作：魔板中央对的4个数作顺时针旋转
被操作：12345678
操作后：17245368
代替操作：交换第1位和第2位，交换第1位和第5位，交换第1位和第6位（第一位实时更新）

于是，我们就可以用三种替换操作直接去操作一维状态下的字符串。

下面是本人所能编出的最短代码，如有除压行外其他简化方法，本人乐意接受。

如觉得这篇题解确实有所帮助，请麻烦支持一下，谢谢。

c++代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
unordered_map<string,string> from;

string mA(string now){      //第一种代替操作
    reverse(now.begin(),now.end());
    return now;
}

string mB(string now){      //第二种代替操作
    for(int i=3;i>0;i--){
        swap(now[i],now[i-1]);
        swap(now[7-i],now[8-i]);
    }
    return now;
}

string mC(string now){      //第三种代替操作
    swap(now[1],now[2]);
    swap(now[1],now[5]);
    swap(now[1],now[6]);
    return now;
}

void bfs(string begin,string end){  //广度优先搜索
    queue<string> que;
    que.push(begin);
    from[begin]="";  //初始为空

    while(que.size()){
        string now=que.front();     //取出队头
        que.pop();

        string m[3]={mA(now),mB(now),mC(now)};  //储存三种操作得到的结果

        for(int i=0;i<3;i++)
            if(!from.count(m[i])){  //此操作得到的字符串没被遍历过
                from[m[i]]=from[now]+char('A'+i);     //储存来源
                if(m[i]==end)
                    return;
                que.push(m[i]);     //插入队列
            }
    }
}

int main(){
    string begin="12345678",end;
    for(int i=0;i<8;i++){
        int x;
        scanf("%d",&x);
        end+=char(x+'0');
    }

    if(begin!=end)
        bfs(begin,end);

    cout<<from[end].size()<<endl<<from[end];
    return 0;
}