1225 八数码难题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题解
查看运行结果
#include<cstdio> #include<cstring> #include<iostream> #include<map> using namespace std; struct node{ int shu[4][4]; int step,xs,ys; }a,b,y; map<string,int>s; int n_best=20;//题目保证有解，大约最大步数为20 bool pan(node x){//判断是否达到目标状态 for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(a.shu[i][j]!=x.shu[i][j]) return 0; return 1; } void dfs(node x){ if(x.step>n_best) return ; string q=""; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) q=q+(char)(x.shu[i][j]+'0');//用到了map if(s[q]<x.step&&s[q]!=0) return ;//避免重搜 s[q]=x.step; if(pan(x)){ n_best=x.step;//记录（因为第一次不一定是最优） return ;//跳出 } x.step++;//步数+ 1，下面用y做temp来dfs if(x.xs<3){//可以向右 y=x; swap(y.shu[x.xs][x.ys],y.shu[x.xs+1][x.ys]);//移动‘0’的位置 y.xs++;//0’的位置 改变了 dfs(y);//下一个状态，dfs，以此类推 } if(x.xs>1){//可以向左 y=x; swap(y.shu[x.xs][x.ys],y.shu[x.xs-1][x.ys]); y.xs--; dfs(y); } if(x.ys<3){//可以向下 y=x; swap(y.shu[x.xs][x.ys],y.shu[x.xs][x.ys+1]); y.ys++; dfs(y); } if(x.ys>1){//可以向上 y=x; swap(y.shu[x.xs][x.ys],y.shu[x.xs][x.ys-1]); y.ys--; dfs(y); } return ; } int main(){ for(int i=1;i<=3;i++) for(int j=1;j<=3;j++){ char dd=getchar(); b.shu[i][j]=dd-'0'; if(dd=='0'){//记录'0'的位置 b.xs=i; b.ys=j; } } for(int i=1;i<=3;i++) a.shu[1][i]=i;//a.shu为目标状态：123804765 a.shu[2][1]=8;a.shu[2][2]=0;a.shu[2][3]=4; a.shu[3][1]=7;a.shu[3][2]=6;a.shu[3][3]=5; b.step=0; dfs(b); printf("%d\n",n_best); return 0; }
紫书官方版解法（很直观）
#include<cstdio> #include<cstring> #include<iostream> #include<set> using namespace std; typedef int State[9]; const int N=1e6+10; State st[N],goal; int dist[N]; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; const int hashsize=1000003; int head[hashsize],next[hashsize]; void init_lookup_table(){memset(head,0,sizeof head);} int hash(State &s){//哈希判重 int v=0; for(int i=0;i<9;i++) v=v*10+s[i]; return v%hashsize; } int try_to_insert(int s){ int h=hash(st[s]); int u=head[h]; while(u){ if(!memcmp(st[u],st[s],sizeof st[s])) return 0; u=next[u]; } next[s]=next[h]; head[h]=s; return 1; } /*set<int>vis;//set判重较慢 void init_lookup_table(){vis.clear();} bool try_to_insert(int s){ int v=0; for(int i=0;i<9;i++) v=v*10+st[s][i]; if(vis.count(v)) return 0; vis.insert(v); return 1; }*/ int bfs(){ init_lookup_table(); int h=1,w=2; while(h<w){ State &s=st[h]; if(!memcmp(s,goal,sizeof s)) return h; int z; for(z=0;z<9;z++) if(!s[z]) break; int x=z/3,y=z%3; for(int i=0;i<4;i++){ int nx=x+dx[i]; int ny=y+dy[i]; int nz=nx*3+ny; if(nx>=0&&nx<3&&ny>=0&&ny<3){ State &t=st[w]; memcpy(&t,&s,sizeof s); t[nz]=s[z]; t[z]=s[nz]; dist[w]=dist[h]+1; if(try_to_insert(w)) w++; } } h++; } return 0; } int main(){ goal[0]=1;goal[1]=2;goal[2]=3;goal[3]=8;goal[4]=0;goal[5]=4;goal[6]=7;goal[7]=6;goal[8]=5; for(int i=0;i<9;i++) scanf("%1d",&st[1][i]); int ans=bfs(); ans>0?printf("%d\n",dist[ans]):printf("-1\n"); return 0; }
双向搜索（bfs）+康托展开
时间：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define N 362881//9!+1 struct node{ int a[3][3]; }d[2][N];//0正向搜索，1反向搜索 const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; int mp[2][N],step[2][N]; int t[2],w[2]={1,1};bool flag; int cantor(int x){ int fac[10]={1,1,2,6,24,120,720,5040,40320,362880},m[10],s(0); for(int i=9;i>=1;i--) m[i]=x%10,x/=10; for(int i=1;i<=9;i++){ int tmp=0; for(int j=i+1;j<=9;j++) if(m[j]<m[i]) tmp++; s+=fac[9-i]*tmp; } return s; } int hash(int a[3][3]){ int x=0,k=1;//康拓是给hash做优化？ for(int i=2;i>=0;i--) for(int j=2;j>=0;j--) x+=a[i][j]*k,k*=10; return cantor(x); } void twobfs(int k){ int x,y; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(!d[k][t[k]].a[i][j]){x=i,y=j;break;} for(int h=0;h<4;h++){ for(int i=0;i<3;i++) for(int j=0;j<3;j++) d[k][w[k]].a[i][j]=d[k][t[k]].a[i][j]; int p=x+dx[h],q=y+dy[h]; if(p>=0&&p<3&&q>=0&&q<3){ swap(d[k][w[k]].a[x][y],d[k][w[k]].a[p][q]); int temp=hash(d[k][w[k]].a); if(mp[k][temp]==-1){ step[k][w[k]]=step[k][t[k]]+1; mp[k][temp]=step[k][w[k]]; if(mp[0][temp]!=-1&&mp[1][temp]!=-1){cout<<mp[0][temp]+mp[1][temp]<<endl;flag=1;return;} w[k]++;//tail } } } t[k]++;//head } int main(){ string str; cin>>str; for(int i=0,k=0;i<3;i++) for(int j=0;j<3;j++) d[0][0].a[i][j]=str[k++]-'0'; d[1][0]=(node){1,2,3,8,0,4,7,6,5}; memset(mp,-1,sizeof mp);//记录状态 mp[0][hash(d[0][0].a)]=mp[1][hash(d[1][0].a)]=0;//起始状态、目标状态 while(!flag) w[0]-t[0]<=w[1]-t[1]?twobfs(0):twobfs(1); return 0; }
------------------------------------------------------------
------------------------------------------------------------
脑补原理
双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点；
而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。
双向广度优先算法相对于广度优先算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！
双向广度优先算法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。
另外需要说明的是，广度优先的顺序能够保证找到的路径就是最短路径！
基于以上思想，我们给出双向广度优先算法编程的基本框架如下：
数据结构：
Queue q1, q2; //两个队列分别用于两个方向的扩展（注意在一般的广度优先算法中，只需要一个队列）
int head[2], tail[2]; //两个队列的头指针和尾指针
（原理摘自网络，看看就好了）
康拓展开
康托展开的公式是 X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，ai为当前未出现的元素中是排在第几个（从0开始）。
主要功能：貌似就是求全排列，具体怎么求自己百度。
代码中的hash+cantor，就是一个判重的功能。cantor只是使hash的功效更强大了些，仅此而已。