魔板

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2170    Accepted Submission(s): 455

Problem Description

在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：

1 2 3 4 8 7 6 5

对于魔板，可施加三种不同的操作，具体操作方法如下：

A: 上下两行互换,如上图可变换为状态87654321 B: 每行同时循环右移一格,如上图可变换为41236785 C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

 

 

Input

每组测试数据包括两行，分别代表魔板的初态与目态。

 

 

Output

对每组测试数据输出满足题意的变换步骤。

 

 

Sample Input

12345678 17245368 12345678 82754631

 

 

Sample Output

C AC

 

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include
           
              6 using namespace std ;  7 const int MAXN = 40321; //由于此题数字1~8，康托展开的所有情况为8!，共40320种  8 const int fac[8] = {
     1,1,2,6,24,120,720,5040}; //康托展开中用到的0~7的阶乘  9 string ans[MAXN]; //存储各状态的变化步骤，预处理完成 10 struct node 11  12 { 13     int a[8]; 14     int n; 15 } u,v; 16 void A(node &t) //A操作 17  18 { 19     std::reverse (t.a , t.a + 8) ; 20  21 } 22 void B(node &t) //B操作 23  24 { 25      std::rotate (t.a , t.a + 3, t.a + 4 ) ; 26      std::rotate (t.a + 4 , t.a + 5 , t.a + 8 ) ; 27 } 28 void C(node &t) //C操作 29  30 { 31     std::swap(t.a[1],t.a[6]); 32     std::swap(t.a[6],t.a[5]); 33     std::swap(t.a[5],t.a[2]); 34  35 } 36 int contor(node &t) //康托展开 37  38 { 39     int tmp, num = 0; 40     for(int i=0; i<8; i++) 41     { 42         tmp = 0; 43         for(int j=i+1; j<8; j++) 44         { 45             if(t.a[j] < t.a[i]) 46             { 47                 tmp++; 48  49             } 50  51         } 52         num += tmp*fac[7-i]; 53  54     } 55     return num; 56  57 } 58 void Init(void) 59  60 { 61     void (*ptr[3])(node&); //定义函数指针 62     ptr[0] = A; 63     ptr[1] = B; 64     ptr[2] = C; //指向对应函数方便处理 65  66     int mark[MAXN] = {
     0}; //设置标记 67     mark[0] = 1; 68  69     for(int i=0; i<8; i++) //由初始状态12345678开始 70     { 71         u.a[i] = i+1; 72  73     } 74     u.n = contor(u); 75  76     queue
            
             que; 77 que.push(u); 78 while(!que.empty()) 79 { 80 u = que.front(); 81 que.pop(); 82 for(int i=0; i<3; i++) //三种变换 83 { 84 v = u; 85 (*ptr[i])(v); 86 v.n = contor(v); //对副本执行操作并康托展开 87 if(mark[v.n] == 0) //重复 88 { 89 char ch = 'A' + i; 90 ans[v.n] = ans[u.n] + ch; //记录步骤 91 92 mark[v.n] = 1; //标记 93 que.push(v); 94 95 } 96 97 } 98 99 }100 101 }102 int main()103 104 {105 //freopen ("a.txt" , "r" , stdin ) ;106 Init();107 char a[10] = { 0},b[10] = { 0};108 while(~ scanf ("%s" , a))109 {110 scanf ("%s" , b) ;111 int n[10];112 for(int i=0; i<8; i++) //把初态置换成12345678113 {114 n[a[i] - '0'] = i+1;115 }116 117 for(int i=0; i<8; i++) //把目标状态相对于初态置换118 {119 u.a[i] = n[b[i] - '0'];120 121 }122 123 cout<
             
              <