hdu 1430 魔板

魔板

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

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

Author

Source

ACM暑期集训队练习赛（三）

Recommend

linle | We have carefully selected several similar problems for you: 1429 1426 1427 1401 1043

第一眼看到这道题，只想到了爆搜的方法，但是这是个八位数，直接标记数字无法进行下去，于是我天真地将其分成两个四位数分开标记，最后当然是华丽的超时。。。。看着眼前欲哭无泪的代码，我决定上网看看各路大神的写法，结果找到了一个貌似很厉害的东东，“康托展开”（详见我的另一篇博客“康托展开”），仔细研究了一番，发现很有道理的样纸，于是仿照网上的代码，完成了自己的。

起始状态ch1虽然不是12345678，但是可以把它看做12345678（状态ss），因而就有一种对应关系存在，用这种对应关系置换最终状态ch2得到状态ch，那么原来ch1->ch2就可以等价为ss->ch了。这样就只需要对ss这个状态进行一次bfs预处理，将答案存下来就ok了。

题意：中文题，很好理解。

附上代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <queue>
  6 #define MAX 50000
  7 using namespace std;
  8 char ch1[10],ch2[10];
  9 bool vis[MAX];   //标记是否出现过这个串
 10 string str[MAX];   //记录最终的变换过程
 11 int f[10]= {1,1,2,6,24,120,720,5040}; //1-7的阶层，康托展开需要用到
 12 
 13 struct node
 14 {
 15     int t;  //记录康托值
 16     char a[10];  //当前的字符串
 17 } s1,s2;
 18 
 19 void getss(int k)   //三种不同的变换规律
 20 {
 21     int i,j;
 22     if(k==0)
 23     {
 24         for(i=0; i<4; i++)
 25         {
 26             s2.a[i]=s1.a[7-i];
 27             s2.a[i+4]=s1.a[3-i];
 28         }
 29     }
 30     else if(k==1)
 31     {
 32         s2.a[0]=s1.a[3];
 33         s2.a[7]=s1.a[4];
 34         for(i=1; i<4; i++)
 35         {
 36             s2.a[i]=s1.a[i-1];
 37             s2.a[i+3]=s1.a[i+4];
 38         }
 39     }
 40     else
 41     {
 42         for(i=0; i<8; i++)
 43             s2.a[i]=s1.a[i];
 44         s2.a[1]=s1.a[6];
 45         s2.a[2]=s1.a[1];
 46         s2.a[5]=s1.a[2];
 47         s2.a[6]=s1.a[5];
 48     }
 49 }
 50 
 51 int xx(char ss[])   //计算康托展开的数字，方法详见“康托展开”博客
 52 {
 53     int i,j,s=0,w;
 54     for(i=0; i<8; i++)
 55     {
 56         w=0;
 57         for(j=i+1; j<8; j++)
 58             if(ss[j]<ss[i])
 59                 w++;
 60         s+=w*f[7-i];
 61     }
 62     return s;
 63 }
 64 
 65 void BFS()   //预处理
 66 {
 67     queue<node> q;
 68     while(!q.empty())
 69         q.pop();
 70     int i,j,n;
 71     char c;
 72     memset(vis,0,sizeof(vis));   //开始所有的数字为0
 73     s1.t=0;    //康托值为0
 74     strcpy(s1.a,"12345678");   //原始数据为12345678
 75     vis[0]=1;    //出现过则标为1
 76     str[0]="";
 77     q.push(s1);   //进入队列
 78     while(!q.empty())
 79     {
 80         s1=q.front();
 81         q.pop();
 82         for(i=0; i<3; i++)
 83         {
 84             getss(i);   //变换后的字符记录在s2.a上
 85             n=xx(s2.a);  //此时的康托值
 86             if(!vis[n])  //通过判断康托值是否出现以此记录这个串是否出现
 87             {
 88                 vis[n]=1;   //这个康托值标记为已出现
 89                 c='A'+i;    //变换的方案
 90                 s2.t=n;     //保存当前串的康托值
 91                 str[n]=str[s1.t]+c;   //记录变换过程
 92                 q.push(s2);
 93             }
 94         }
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int i,j,s;
101     char ch[10];
102     BFS();       //预处理打表
103     while(~scanf("%s %s",ch1,ch2))
104     {
105         for(i=0; i<8; i++)   //建立对应关系，记录起始数据每个数的位置
106             ch[ch1[i]-'0']=i+1+'0';
107         for(i=0; i<8; i++)   //置换，利用位置变换形成新的字符串
108             ch2[i]=ch[ch2[i]-'0'];
109         s=xx(ch2);      //计算康托展开的数
110         cout<<str[s]<<endl;   //根据康托展开记录的数字查找
111     }
112     return 0;
113 }