1 /*  2 PROB:msquare  3 LANG:C++  4 */  5   6 #include <iostream>  7 #include <vector>  8 #include <algorithm>  9 #include <map> 10 #include <queue> 11 #include <cstdio> 12 using namespace std; 13  14 struct node 15 { 16     vector<int> seq; 17     int step; 18     vector<int> opt; 19     node(vector<int> x,int m,vector<int> o,int op):seq(x),step(m),opt(o) 20     { 21         opt.push_back(op); 22     } 23 }; 24  25 map<vector<int>,int> M; 26 queue<node> Q; 27 vector<int> a;      //tmp2 28 vector<int> A;      //init 29 vector<int> y;      //tmp1 30 vector<int> B;      //goal 31 vector<int> ans; 32 vector<int> yy; 33 int b[10]; 34  35 bool same() 36 { 37     for (int i=0;i<8;i++) 38         if (y[i]!=b[i]) 39             return false; 40     return true; 41 } 42  43 int main() 44 { 45     freopen("msquare.in","r",stdin); 46     freopen("msquare.out","w",stdout); 47  48     B.clear(); 49     a.clear(); 50     A.clear(); 51     for (int i=0;i<=3;i++) 52     { 53         cin>>b[i]; 54         A.push_back(i+1); 55     } 56     for (int i=7;i>=4;i--) 57     { 58         cin>>b[i]; 59         A.push_back(i+1); 60     } 61     for (int i=0;i<8;i++) 62         B.push_back(b[i]); 63  64     //for (int i=0;i<8;i++) 65     //    cout<<B[i]<<" "<<A[i]<<endl; 66  67     //A[0]=1;     A[1]=2;     A[2]=3;     A[3]=4; 68     //A[4]=8;     A[5]=7;     A[6]=6;     A[7]=5; 69     Q.push(node(A,0,a,0)); 70     M.insert(pair<vector<int>,int>(A,1)); 71     while (!Q.empty()) 72     { 73         node tmp=Q.front(); 74         Q.pop(); 75         int st=tmp.step; 76         //cout<<"step  "<<st<<endl; 77         y=tmp.seq; 78         yy=tmp.opt; 79         if (same()) 80         { 81             ans.clear(); 82             ans=tmp.opt; 83             cout<<st<<endl; 84             for (int i=1;i<=st;i++) 85             { 86                 char ch=ans[i]+‘A‘-1; 87                 cout<<ch; 88             } 89             cout<<endl; 90             break; 91         } 92         else 93         { 94             //opr1 95             a=y; 96             swap(a[0],a[4]); 97             swap(a[1],a[5]); 98             swap(a[2],a[6]); 99             swap(a[3],a[7]);100             if (!M.count(a))101             {102                 M.insert(pair<vector<int>,int>(a,1));103                 Q.push(node(a,st+1,yy,1));104             }105             //opr2106             a=y;107             int t1=a[3],t2=a[7];108             a[3]=a[2];  a[7]=a[6];109             a[2]=a[1];  a[6]=a[5];110             a[1]=a[0];  a[5]=a[4];111             a[0]=t1;    a[4]=t2;112             if (!M.count(a))113             {114                 M.insert(pair<vector<int>,int>(a,1));115                 Q.push(node(a,st+1,yy,2));116             }117             //opr3118             a=y;119             int tm=a[1];120             a[1]=a[5];  a[5]=a[6];  a[6]=a[2];  a[2]=tm;121             if (!M.count(a))122             {123                 M.insert(pair<vector<int>,int>(a,1));124                 Q.push(node(a,st+1,yy,3));125             }126         }127     }128 129     return 0;130 }