魔板

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

 #include <iostream>

 #include <string>

 #include <algorithm>

 #include <queue>

 #include<stdio.h>

 using namespace std ;

 const int MAXN = ; //由于此题数字1~8，康托展开的所有情况为8!，共40320种

 const int fac[] = {,,,,,,,}; //康托展开中用到的0~7的阶乘

 string ans[MAXN]; //存储各状态的变化步骤，预处理完成

 struct node

 {

     int a[];

     int n;

 } u,v;

 void A(node &t) //A操作

 {

     std::reverse (t.a , t.a + ) ;

 }

 void B(node &t) //B操作

 {

      std::rotate (t.a , t.a + , t.a +  ) ;

      std::rotate (t.a +  , t.a +  , t.a +  ) ;

 }

 void C(node &t) //C操作

 {

     std::swap(t.a[],t.a[]);

     std::swap(t.a[],t.a[]);

     std::swap(t.a[],t.a[]);

 }

 int contor(node &t) //康托展开

 {

     int tmp, num = ;

     for(int i=; i<; i++)

     {

         tmp = ;

         for(int j=i+; j<; j++)

         {

             if(t.a[j] < t.a[i])

             {

                 tmp++;

             }

         }

         num += tmp*fac[-i];

     }

     return num;

 }

 void Init(void)

 {

     void (*ptr[])(node&); //定义函数指针

     ptr[] = A;

     ptr[] = B;

     ptr[] = C; //指向对应函数方便处理

     int mark[MAXN] = {}; //设置标记

     mark[] = ;

     for(int i=; i<; i++) //由初始状态12345678开始

     {

         u.a[i] = i+;

     }

     u.n = contor(u);

     queue<node>que;

     que.push(u);

     while(!que.empty())

     {

         u = que.front();

         que.pop();

         for(int i=; i<; i++) //三种变换

         {

             v = u;

             (*ptr[i])(v);

             v.n = contor(v); //对副本执行操作并康托展开

             if(mark[v.n] == ) //重复

             {

                 char ch = 'A' + i;

                 ans[v.n] = ans[u.n] + ch; //记录步骤

                 mark[v.n] = ; //标记

                 que.push(v);

             }

         }

     }

 }

 int main()

 {

     //freopen ("a.txt" , "r" , stdin ) ;

     Init();

     char a[] = {},b[] = {};

     while(~ scanf ("%s" , a))

     {

         scanf ("%s" , b) ;

         int n[];

         for(int i=; i<; i++) //把初态置换成12345678

         {

             n[a[i] - ''] = i+;

         }

         for(int i=; i<; i++) //把目标状态相对于初态置换

         {

             u.a[i] = n[b[i] - ''];

         }

         cout<<ans[contor(u)]<<endl; //输出由12345678到目标态的步骤

     }

     return ;

 }

巴特西

hdu.1430.魔板(bfs + 康托展开）

魔板

最新文章

热门文章