16哈理工新生赛 E Nine Digits （BFS+康拓展开）

妖狐艹你老母 2022-07-14 09:42 129阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>题目链接：<a href="http://acm.hrbust.edu.cn/index.php?m=ProblemSet&amp;a=showProblem&amp;problem_id=2297" rel="nofollow">点击打开链接</a> Nine Digits</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 3000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 69(19 users)</td> 
 <td>Total Accepted: 16(12 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td><img alt="" src="http://acm.hrbust.edu.cn/contests/attached/image/20161125/20161125122308_33369.jpg"></td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td> 多组数据，每组测试数据输入9个整数，为1-9的一个全排列。初始状态会被描述为 1 2 3 4 5 6 7 8 9 </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td> 输出所需要的最小移动步数。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td> 1&nbsp;2&nbsp;3&nbsp;4&nbsp;5&nbsp;6&nbsp;7&nbsp;8&nbsp;9 9&nbsp;8&nbsp;7&nbsp;6&nbsp;5&nbsp;4&nbsp;3&nbsp;2&nbsp;1 </td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td> 0 12 </td> 
 </tr> 
 <tr> 
 <td>Source</td> 
 </tr> 
 <tr> 
 <td>2016级新生程序设计全国邀请赛</td> 
 </tr> 
 </tbody> 
</table>

题解：

一看题目，我就想到BFS，就是把所有情况搜出来，也就是9的阶乘362880种情况。但是由于不能够建立一个九位数的数组来保存这些数据，因此这里需要用到康托展开。

康托展开的使用范围是对于n个数的排列进行状态的压缩和存储,例如要对9的全排列进行判重.没有必要开一个10的9次幂的数组，因此它有362880中情况。因此其思想就是相当于一个哈希函数。一个排列它所对应的位置就是它排的是第几大。比如321，对应的值就是6，因为前面有123,132,213,231,312比它小。下面的cantor( )函数就是。

做完康托展开后，就要实现四种情况的变换，这个也比较简单，使用四个函数来实现即可，但是写的过程需要特别小心。

AC代码：

#include<iostream>
 #include<cstdio>
 #include<queue>
 using namespace std;
 const int MAX=362880;
 int s[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
 int jie[10]={0,1,2,6,24,120,720,5040,40320,362880};
 int visit[MAX];
 int len[MAX];
 int four[4];
 
 int lu(int num)
 {
 int result;
 result=num%s[4];
 result+=((num/s[5])%10)*s[4];
 result+=num/s[8]*s[5];
 result+=((num/s[6])%10)*s[6];
 result+=((num/s[4])%10)*s[7];
 result+=((num/s[7])%10)*s[8];
 return result;
 }
 
 int ru( int num ) 
 { 
 int result = num/s[5]*s[5]; 
 result += num/s[1]%10; 
 result += num/s[4]%10*s[1]; 
 result += num/s[2]%10*s[2]; 
 result += num%10*s[3]; 
 result += num/s[3]%10*s[4]; 
 
 return result; 
 } 
 
 int ld( int num ) 
 { 
 int result = num/s[6]*s[6] + num%10; 
 
 result += num/s[2]%10*s[1]; 
 result += num/s[5]%10*s[2]; 
 result += num/s[3]%10*s[3]; 
 result += num/s[1]%10*s[4]; 
 result += num/s[4]%10*s[5]; 
 
 return result; 
 } 
 
 int rd( int num ) 
 { 
 int result = num % s[3] + num/s[8]*s[8]; 
 
 result += num/s[4]%10*s[3]; 
 result += num/s[7]%10*s[4]; 
 result += num/s[5]%10*s[5]; 
 result += num/s[3]%10*s[6]; 
 result += num/s[6]%10*s[7]; 
 
 return result; 
 } 
 int cantor(int key) //康拓展开 
 {
 int result,temp[9];
 for(int i=8;i>=0;i--)
 {
 temp[i]=key%10;
 key=key/10;
 }
 result=0;
 
 for(int i=0;i<8;i++)
 {
 int tot=0;
 for(int j=i+1;j<9;j++)
 if(temp[j]<temp[i])
 tot++;
 result+=tot*jie[8-i];
 }
 return result;
 }
 int key2[4];
 int start=123456789;
 queue<int>que;
 int main()
 {
 
 
 int temp;
 int key1;
 len[0]=0;
 que.push(start);
 visit[0]=1;
 while(!que.empty())
 {
 temp=que.front();
 que.pop();
 key1=cantor(temp);
 four[0]=lu(temp);
 
 four[1]=ru(temp);
 
 four[2]=ld(temp);
 
 four[3]=rd(temp);
 
 for(int i=0;i<4;i++)
 {
 key2[i]=cantor(four[i]);
 if(!visit[key2[i]])
 {
 visit[key2[i]]=1;
 que.push(four[i]);
 
 len[key2[i]]=len[key1]+1;
 }
 }
 }
 
 int input[9];
 while(~scanf("%d",&input[0]))
 {
 temp=input[0];
 for(int i=1;i<9;i++)
 {
 scanf("%d",&input[i]);
 temp=input[i]+temp*10;
 }
 printf("%d\n",len[cantor(temp)]);
 }
 return 0;
 }