题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043
题目大意:传统八数码问题
解题思路:就是从“12345678x”这个终点状态开始反向BFS,将各个状态记录下来,因为数字太大所以用康托展开将数字离散化。
代码:
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 const int N=4e5+5; 10 11 int vis[N]; 12 string path[N]; 13 char map[15]; 14 char index[5]="udrl";//因为是逆向所以方向要反一下 15 int d[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; 16 int fac[15]={1,1,2,6,24,120,720,5040,40320}; 17 18 struct node{ 19 char num[10]; 20 int pos; 21 string path; 22 }pre,now; 23 24 //求康托展开值 25 int cantor(char s[]){ 26 int sum=0; 27 int n=strlen(s); 28 for(int i=0;i<n;i++){ 29 int cnt=0; 30 for(int j=i+1;j<n;j++){ 31 if(s[i]>s[j]) 32 cnt++; 33 } 34 sum+=cnt*fac[n-i-1]; 35 } 36 return sum+1; 37 } 38 //从12345678x逆向BFS打表 39 void bfs(){ 40 queue<node>q; 41 now.pos=8; 42 for(int i=0;i<8;i++) 43 now.num[i]=i+1+'0'; 44 now.num[8]='0'; 45 now.num[9]='