题目描述
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有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个字符。

Sample Input

2 6 8 4 5 7 3 1

Sample Output

7
BCABCCB 

思路：用8位整数来记录状态，在处理的时候先转换为字符数组形式，处理完之后再转换回整数。步骤用vector记录。

#include <cstdio>
#include <queue>
#include <unordered_map>
using namespace std;

int goal = 0;
struct node {
    int num, step;
    vector<char> v;
} Node;
unordered_map<int, bool> inq; //标记是否入队

void change(char str[], int way) { //三种操作
    if (way == 0) {
        char temp;
        for (int i = 0; i < 4; i++) {
            temp = str[i];
            str[i] = str[7 - i];
            str[7 - i] = temp;
        }
    } else if (way == 1) {
        char temp = str[3];
        for (int i = 3; i > 0; i--) {
            str[i] = str[i - 1];
        }
        str[0] = temp;
        temp = str[4];
        for (int i = 4; i < 7; i++) {
            str[i] = str[i + 1];
        }
        str[7] = temp;
    } else if (way == 2) {
        char temp = str[1];
        str[1] = str[6];
        str[6] = str[5];
        str[5] = str[2];
        str[2] = temp;
    }
}

void BFS() {
    queue<node> Q;
    Node.num = 12345678;//起始状态
    Node.step = 0;
    Q.push(Node);
    inq[12345678] = true;
    char temp1[10];
    int temp2;
    while (!Q.empty()) {
        node top = Q.front();
        Q.pop();
        if (top.num == goal) { //得到目标状态
            printf("%d\n", top.step);
            for (int i = 0; i < top.step; i++) {
                if (i % 60 == 0 && i != 0) {
                    printf("%c\n", top.v[i]);
                } else {
                    printf("%c", top.v[i]);
                }
            }
        }
        for (int i = 0; i < 3; i++) {
            sprintf(temp1, "%d", top.num); //数字转换为字符数组
            change(temp1, i); //三种操作
            sscanf(temp1, "%d", &temp2); //再将字符数组转换为数字
            if (!inq[temp2]) {
                Node.num = temp2;
                Node.step = top.step + 1;
                Node.v = top.v;
                Node.v.push_back(i + 'A'); //记录步骤
                Q.push(Node);
                inq[temp2] = true;
            }
        }
    }
}


int main() {
    int n = 0;
    for (int i = 0; i < 8; i++) {
        scanf("%d", &n);
        goal = goal * 10 + n;
    }
    BFS();
    return 0;
}