USACO 魔板 Magic Squares

题目背景

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

输入输出样例

输入样例#1：

2 6 8 4 5 7 3 1

输出样例#1：

7 
BCABCCB

  1 #include<iostream>
  2 #include<string.h>
  3 #include<algorithm>
  4 #include<limits.h>
  5 #include<stdio.h>
  6 using namespace std;
  7 int fac[10]={1,1,2,6,24,120,720,5040,40320};
  8 int s[10]={0,1,2,3,4,8,7,6,5};
  9 int w[10];
 10 int Std[10];
 11 int book[100000];
 12 int Stdhash;
 13 int head=1;
 14 int tail=1;
 15 int len;
 16 char oput[100000];
 17 struct node
 18 {
 19     int last;
 20     int num;
 21     char ch;
 22 }f[100000];
 23 int hash(int p[])
 24 {
 25     int cnt,ans=0;
 26     for(int i=1;i<=8;++i)
 27     {
 28         cnt=0;
 29         for(int j=i+1;j<=8;++j)
 30         {
 31             if(p[i]>p[j])
 32             {
 33                 ++cnt;
 34             }
 35         }
 36         ans+=cnt*fac[8-i];
 37     }
 38     return ans;
 39 }
 40 void rehash(int hashnum)
 41 {
 42     int p[10],buf,cnt;
 43     memset(p,0,sizeof(p));
 44     for(int i=8;i>=1;--i)
 45     {
 46         cnt=0;
 47         buf=(int)hashnum/fac[i-1];
 48         for(int j=1;j<=8;++j)
 49         {
 50             if(!p[j])
 51             {
 52                 ++cnt;
 53                 if(cnt==buf+1)
 54                 {
 55                     s[8-i+1]=j;
 56                     p[j]=1;
 57                     break;
 58                 }
 59             }
 60         }
 61         hashnum%=fac[i-1];
 62     }
 63 }
 64 int A()
 65 {
 66     for(int i=1;i<=4;++i)
 67     {
 68         w[i]=s[i+4];
 69         w[i+4]=s[i];
 70     }
 71     return hash(w);
 72 }
 73 int B()
 74 {
 75     for(int i=1;i<=4;++i)
 76     {
 77         w[i%4+1]=s[i];
 78         w[i%4+5]=s[i+4];
 79     }
 80     return hash(w);
 81 }
 82 int C()
 83 {
 84     for(int i=1;i<=8;++i)
 85         w[i]=s[i];
 86     w[2]=s[6];
 87     w[3]=s[2];
 88     w[7]=s[3];
 89     w[6]=s[7];
 90     return hash(w);
 91 }
 92 int main()
 93 {
 94     for(int i=1;i<=4;++i)
 95     {
 96         cin>>Std[i];
 97     }
 98     for(int i=8;i>=5;--i)
 99     {
100         cin>>Std[i];
101     }
102     Stdhash=hash(Std);
103     f[1].ch=' ';
104     f[1].last=1;
105     f[1].num=hash(s);
106     book[f[1].num]=1;
107     while(head<=tail)
108     {
109         if(f[head].num==Stdhash)
110         {
111             int t=head;
112             while(f[t].last!=t)
113             {
114                 oput[++len]=f[t].ch;
115                 t=f[t].last;
116             }
117             cout<<len<<'
';
118             for(int i=len;i>=1;--i) cout<<oput[i];
119             break;
120         }
121         rehash(f[head].num);
122         int a=A();
123         int b=B();
124         int c=C();
125         if(!book[a])
126         {
127             ++tail;
128             f[tail].ch='A';
129             f[tail].last=head;
130             f[tail].num=a;
131             book[a]=1;
132         }
133         if(!book[b])
134         {
135             ++tail;
136             f[tail].ch='B';
137             f[tail].last=head;
138             f[tail].num=b;
139             book[b]=1;
140         }
141         if(!book[c])
142         {
143             ++tail;
144             f[tail].ch='C';
145             f[tail].last=head;
146             f[tail].num=c;
147             book[c]=1;
148         }
149         ++head;
150     }
151     return 0;
152 }