【广搜】魔板
题目描述
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.
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.
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 }