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
*/