Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:

In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.

Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:

• 'A': exchange the top and bottom row,
• 'B': single right circular shifting of the rectangle,
• 'C': single clockwise rotation of the middle four squares.

Below is a demonstration of applying the transformations to the initial squares given above:

All possible configurations are available using the three basic transformations.

You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.

PROGRAM NAME: msquare

INPUT FORMAT

A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.

SAMPLE INPUT (file msquare.in)

2 6 8 4 5 7 3 1 

OUTPUT FORMAT

SAMPLE OUTPUT (file msquare.out)

7
BCABCCB

题意：
魔方的初始状态时1 2 3 4 5 6 7 8，魔方有三种操作方法，A， B， C。对与给出的目的状态。求出到达目的状态最佳的操作序列。

代码如下：

/*
LANG: C
TASK: msquare
*/
#include<stdio.h>
#define maxn 40320
int cmb[7] = {5040, 720, 120, 24, 6, 2, 1};//7到0的阶乘，即全排列 
int t[8], queue[maxn], index = 0;
char result[1000];
struct hash
{
    int magic, parent;
    char work;
}hash[maxn];
void read()
{
    int i;
    for (i = 0; i < 8; i++)
    {
        scanf("%d", &t[i]);
    }
}
int encode(int *tmp)//对每种状态（序列）hash。 
{
    int i, j, has = 0, pre;
    for (i = 0; i < 7; i++)
    {
        for (pre = 0, j = i + 1; j < 8; j++)//找出i后面比tmp[i]小的个数 
        {
            if (tmp[j] < tmp[i])
            {
                pre++;
            }            
        }
        has += pre * cmb[i];//变进制的哈希 
    }
    return has;
}
int from(int num, int * f)//对魔方的十进制数还原为序列 
{
    int n = 7;
    while (num)
    {
        f[n--] = num % 10;
        num /= 10;
    }
}
int to(int *tmp)//对魔方的状态（序列）生成一个十进制数 
{
    int i, num = 0;
    for (i = 0; i < 8; i++)
    {
        num = num * 10 + tmp[i];
    }
    return num;
}
void swap(int i, int j, int * tmp)//交换两个元素 
{
    tmp[i] ^= tmp[j], tmp[j] ^= tmp[i], tmp[i] ^= tmp[j];
}
int deal(int th, int * tmp, int parent)//对魔方的旋转操作 
{
    int code, i, j;
    if (th == 0)
    {
        for (i = 0; i < 4; i++)
        {
            swap(i, 7 - i, tmp);
        }
    }
    else if (th == 1)
    {
        for (i = 3, j = 4; i > 0; i--, j++)
        {
            swap(i, i - 1, tmp), swap(j, j + 1, tmp);
        }
    }
    else if (th == 2)
    {
        swap(1, 6, tmp), swap(6, 5, tmp), swap(5, 2, tmp);
    }
    code = encode(tmp);//对操作后的序列编码 
    if (hash[code].magic)
    {
        return -1;
    }
    else
    {
        hash[code].magic = to(tmp);//生成十进制的序列 
        hash[code].parent = parent;//保存父节点的下标 
        hash[code].work = 'A' + th;//保存该操作 
        return code;
    }
}
void copy(int * f, int *tmp)//将当前魔方序列复制到tmp，用tmp做下一步操作 
{
    int i;
    for (i = 0; i < 8; i++)
    {
        tmp[i] = f[i];
    }
}
int Bfs()
{
    int i, target, left, right, code, pre, parent, tmp[8], f[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    //对第一个序列编码 
    target = encode(t);
    code = encode(f);
    hash[code].magic = to(f), hash[code].parent = -1;
    left =  right = 0;
    queue[right++] = code;
    while (left < right)
    {
        pre = queue[left++];
        from(hash[pre].magic, f);//还原模仿序列 
        parent = pre;
        for (i = 0; i < 3; i++)
        {
            copy(f, tmp);
            code = deal(i, tmp, parent);
            if (code != -1)
            {
                queue[right++] = code;
            }
            if (hash[target].magic)//如果目的已被搜索过，返回目标的下标结果 
            {
                return target;
            }
        }
    }
}
void save(int pre, int n)//回溯保存结果 
{
    if (pre < 0)
    {
        printf("%d\n", n - 1);
        return;
    }
    save(hash[pre].parent, n + 1);
    if (pre > 0)
    {
        result[index++] = hash[pre].work;
    }
}
void print()
{
    int i;
    for (i = 0; result[i] != 0; i++)
    {
        printf("%c", result[i]);
        if ((i + 1) % 60 == 0)
        {
            printf("\n");
        }
    }
    if (i % 60 != 0)
    {
        printf("\n");
    }
    if (i == 0)//如果不用改变魔方，也占一空行 
    {
        printf("\n");
    }
}
int main()
{
    freopen("msquare.in", "r", stdin), freopen("msquare.out", "w", stdout);
    read();
    save(Bfs(), 0);
    result[index] = 0;
    print();
    fclose(stdin), fclose(stdout);
    //system("pause");
    return 0;
}
/*
8 7 6 5 4 3 2 1
*/