题目描述
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: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:
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.
输入
A single line with eight space-separated integers (a permutation of {1..8}) that are the target configuration.
输出
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.
样例输入
2 6 8 4 5 7 3 1
样例输出
7 BCABCCB
【题意】
求把8个排好的数字经过一系列操作后变成目标状态的最快的操作方法。
【思路】
这道题是一道非常经典的BFS题目，BFS所面临的最大问题是判断重复。显然，如果每次判断重复都扫描一次队列，搜索的效率将非常低，会提高一个指数级，所以一般宽度搜索的判断重复都是运用数组来实现的，那么数组下标就需要用一个Hash函数来计算出来。因此，设计
本题Hash函数的设计，我们容易想到将8个数字按顺时针顺序组合成8进制（每个数字都要减一）的8位基数。但是，这里最大的八进制数76543210，转换成十进制为16434824，也就是说要开大小为16434824的数组，如果数组强制空间限制，那么，数组的下标会越界。
这里我们引入康拓展开，即将一个排列对应成它在全排列中的序数，这样就不会MLE了。
如{1,2,3,4……n}表示1,2,3，……n的一个排列，如{1,2,3}按从小到大排列，一共有6个：123,132,213,231,312,321，分别代表数字1,2,3,4,5,6，也就是把十进制与一个排列对应起来。它们之间的对应关系可由康拓展开来找到。
如想知道321是{1,2,3}中第几大的数，可以这样考虑：第一位是3，当第一位的数字小于3时，对应的排序数都小于321，如123,213，则小于3的数有1,2，所以有2*2！个；再看小于第二位数字2，小于2的数只有一个就是1，所以有1*1！= 1 。因此小于321的{1,2,3}排列共有2*2!+1*1!=5个，所以321是第六大的数。
再如1324是{1,2,3,4}排列数中第几大的数？第一位数字是1，小于1的数没有，是0个，即0*3！；第二位数字是3，小于3的数有1,2，但1已经在第一位上了，所以只有一个数2，即1*2！；第三位数字是2，小于2的数是1，但1在第一位，所以有0个数，即0*1！。因此比1324小的排列有0*3！+1*2！+0*1！=2个，所以1324是第三大的数。
设step[]记步数；记i的父结点为prt[i],a[i]表示第i个序列采用那种变换。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int F[] = {1,1,2,6,24,120,720,5040}; //F[i] = i!
4 int g,st,prt[50005],b[1000000],step[50005];
5 char a[50005];
6 struct mb{
7 int a[2][4];
8 }start , goal,q[90000];
9 int Turn(mb x) { // 康拓展开
10 int res =0 ,t[8] , s;
11 for(int i=0;i<4;i++) // 构成序列
12 t[i] = x.a[0][i] ;
13 for(int i=3;i>=0;i--)
14 t[7-i] = x.a[1][i] ;
15 for(int i=0;i<8;i++){
16 s = 0 ;
17 for(int j=i+1;j<=7;j++){ //找后面小于t[i]的值
18 if ( t[j] < t[i] ) s++;
19 }
20 res += F[7-i] * s;
21 }
22 return res ;
23 }
24 mb Change(int way,int num){ //三种基本操作
25 mb temp ;
26 if ( way == 1 ){ // A
27 for(int i=0;i<4;i++){
28 temp.a[0][i] = q[num].a[1][i];
29 temp.a[1][i] = q[num].a[0][i];
30 }
31 return temp;
32 }
33 else if( way == 2 ){ // B
34 temp.a[0][0] = q[num].a[0][3];
35 temp.a[1][0] = q[num].a[1][3];
36 for(int i=1;i<4;i++){
37 temp.a[0][i] = q[num].a[0][i-1];
38 temp.a[1][i] = q[num].a[1][i-1];
39 }
40 return temp;
41 }else{ // C
42 temp.a[0][0] = q[num].a[0][0];
43 temp.a[0][3] = q[num].a[0][3];
44 temp.a[1][0] = q[num].a[1][0];
45 temp.a[1][3] = q[num].a[1][3];
46
47 temp.a[0][1] = q[num].a[1][1];
48 temp.a[0][2] = q[num].a[0][1];
49 temp.a[1][2] = q[num].a[0][2];
50 temp.a[1][1] = q[num].a[1][2];
51
52 return temp;
53 }
54 }
55 void Print(int num){ //递归输出结果
56 if ( num == 1 ) return ;
57 Print(prt[num]);
58 printf("%c",a[num]);
59 }
60 void BFS(){
61 int Head = 1 , Tail = 1 ,t ;
62 mb temp ;
63 q[1] = start ;
64 step[1] = 0 ;
65 prt[1] = 1 ;
66 while ( Head <= Tail ){
67 for(int i=1;i<=3;i++){
68 temp = Change(i,Head) ;
69 t = Turn(temp) ;
70 if( !b[t] ){
71 q[++Tail] = temp ;
72 step[Tail] = step[Head] + 1 ;
73 b[t] = 1 ;
74 prt[Tail] = Head;
75 a[Tail] = char('A' + i -1 );
76 if( t==g ){
77 cout << step[Tail] << endl;
78 Print(Tail);
79 return ;
80 }
81 }
82 }
83 Head ++ ;
84 }
85 }
86 int main()
87 {
88 for(int i=0;i<4;i++){
89 start.a[0][i] = i+1 ;
90 }
91 for(int i=3;i>=0;i--){
92 start.a[1][i] = 8-i;
93 }
94 st = Turn(start) ;
95 b[st] = 1 ;
96 for(int i=0;i<4;i++){
97 cin >> goal.a[0][i];
98 }
99 for(int i=3;i>=0;i--){
100 cin >> goal.a[1][i];
101 }
102 g = Turn(goal);
103 if( g==st ){
104 cout << 0 ;return 0;
105 }
106 BFS();
107 return 0;
108 }
魔板