Magic Squares
IOI'96 
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:
1
2
3
4
8
7
6
5
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:
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
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

    

        

            
Line 1:
            
A single integer that is the length of the shortest transformation sequence.
        
        

            
Line 2:
            
The lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line.
        
    

SAMPLE OUTPUT (file msquare.out)
7
BCABCCB

USER: wang yucao [wangyuc2]
TASK: msquare
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3136 KB]
   Test 2: TEST OK [0.000 secs, 3132 KB]
   Test 3: TEST OK [0.000 secs, 3136 KB]
   Test 4: TEST OK [0.000 secs, 3128 KB]
   Test 5: TEST OK [0.043 secs, 3256 KB]
   Test 6: TEST OK [0.076 secs, 3260 KB]
   Test 7: TEST OK [0.140 secs, 3260 KB]
   Test 8: TEST OK [0.184 secs, 3264 KB]

All tests OK.
YOUR PROGRAM ('msquare') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.
[code]
/*
ID: wangyuc2
PROB:msquare
LANG: C++
*/
/*
这道题是BFS+Hash
在做哈希时，以为8的全排列为40320，所以找到序列是全排列中第几个元素就可以。
介绍一下字符串的一种hash 函数，对这题非常有用。如果叙述不清，请参看05年集训队李羽修的论文。
对于一种排列方式（可视为是一个字符串），计算它在所有排列方式中排第ｘ位，这样就可以做到一一对应。对其从右往左数的第i位进行如下操作：
计算i位置后比第i位小的字符个数p。
        x=x+(i-1)!*ｐ。
最后，x=x+1 。
X即计算出。
用一个布尔数组used来判重，用整形数组a[40500][2]来记录具体路径，我这里a[i][0]记录的是hash值为i的魔板状态的前一步的hash值，a[i][1]记录从上一状态得到hash值为i的魔板状态的变化方法。
这样在输出时只需从后往前找，一直找到a[1][0]=0结束，然后逆序输出即可。
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <queue>
#include <stack>
#define cin fin
using namespace std;
ifstream fin("msquare.in");
ofstream fout("msquare.out");
int power(int a)
{
 int s=1;
 for(int i=a;i>0;i--)
    s*=i;
 return s;
}
int hashf(string s)
{
 int a=0,t;
 for(int i=0;i<7;i++){
    t=0;
    for(int j=i+1;j<8;j++) if(s[j]<s[i]) t++;
    a+=power(7-i)*t;
 }
 return ++a;
}
int main()
{
 int i,j,k,n;
 bool used[40500];
 int a[40500][2];
 char temp;
 string s,st,s1;
 queue<string> q;
 s.assign("12345678");
 memset(used,false,sizeof(used));
 st.assign(s);
 for(i=0;i<8;i++)
    cin>>st[i];
//  reverse(&st[4],st.end());
 q.push(s);
 used[1]=true;
 a[1][0]=0;a[1][1]=0; //0为之前数，1为决策
 while(!q.empty())
 {
    s.assign(q.front());
    q.pop();
    k=hashf(s);
    if(!s.compare(st)) break;
    s1.assign(s);               //A
    reverse(s1.begin(),s1.end());       
    j=hashf(s1);
    if(!used[j] && a[k][1]!=1){
     q.push(s1);
     used[j]=true;
     a[j][0]=k;
     a[j][1]=1;
    }
    s1[0]=s[3];s1[3]=s[2];s1[2]=s[1];s1[1]=s[0];       //B
    s1[7]=s[4];s1[4]=s[5];s1[5]=s[6];s1[6]=s[7];
    j=hashf(s1);
    if(!used[j]){
     q.push(s1);
     used[j]=true;
     a[j][0]=k;
     a[j][1]=2;
    }
    s1.assign(s);               //C
    s1[1]=s[6];s1[2]=s[1];s1[5]=s[2];s1[6]=s[5];
    j=hashf(s1);
    if(!used[j]){
     q.push(s1);
     used[j]=true;
     a[j][0]=k;
     a[j][1]=3;
    }
 }
 stack<char> S;
 while(k!=0){
  
    S.push(char(a[k][1]+64));
    k=a[k][0];
 }
 S.pop();
 fout<<S.size()<<endl;
 while(!S.empty()){
    temp=S.top();
    S.pop();
    fout<<temp;
 }
 fout<<endl;
 return 0;
}
[/code]