感受一下不同做法的时间 1.map+单向bfs 125ms #include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; string st,aim=" 123804765",s,si; char x; map<string,int>p; queue<string>q; queue<int>t; int main() { cin>>st; st=' '+st; q.push(st); p[st]=1; t.push(0); while(!q.empty()) { s=q.front(); int step=t.front(); t.pop();q.pop(); if(s==aim) { cout<<step<<endl; return 0; } si=s; int pi=si.find("0"); if(pi+3<=9) { x=si[pi+3];si[pi+3]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi-3>=1) { x=si[pi-3];si[pi-3]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi+1<=9&&pi!=3&&pi!=6) { x=si[pi+1];si[pi+1]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } si=s; if(pi-1>=1&&pi!=7&&pi!=4) { x=si[pi-1];si[pi-1]=si[pi];si[pi]=x; if(p[si]==0) { q.push(si);t.push(step+1); p[si]=1; } } } } 2.康托展开+单向bfs 16ms #include<iostream> #include<cstdio> #include<cstring> #define maxn 1000100 #define maxx 50000100 #define modd 1000003 using namespace std; int qi[maxn],head,tail,step[maxn],q[maxn]; int qg[maxn],sp=123804765; bool f[maxx]; int KT(int sw) { int g[10],i=9,sum=0; memset(g,0,sizeof(g)); while(sw>0) { g[i]=sw%10; i--; sw=sw/10; } sum=g[9]*9*8*7*6*5*4*3*2+g[8]*8*7*6*5*4*3*2+g[7]*7*6*5*4*3*2+ g[6]*6*5*4*3*2+g[5]*5*4*3*2+g[4]*4*3*2+g[3]*3*2+g[2]*2+g[1]; return sum; } int sswap(int sw,int x,int y) { int temp[10],i=9,tmp; memset(temp,0,sizeof(temp)); while(sw>0) { temp[i]=sw%10; i--; sw=sw/10; } tmp=temp[x]; temp[x]=temp[y]; temp[y]=tmp; sw=0; for(i=1;i<=9;i++) sw=sw*10+temp[i]; return sw; } int find(int s) { int p=9,k; while(s>0) { k=s%10; if(k==0)return p; p--; s=s/10; } } int main() { int s,ssi,ss,st; cin>>s; if(s==sp) { cout<<0; return 0; } int p=find(s); qg[++tail]=s; qi[tail]=p; while(head<tail) { p=qi[++head]; ss=qg[head]; //printf("%d ",ss); if(p-1>=1&&p!=4&&p!=7) { ssi=ss; st=sswap(ssi,p,p-1); if(st==sp) { q[++tail]=head; cout<<step[head]+1<<" "; return 0; } if(f[KT(st)]==0) { f[KT(st)]=1; qg[++tail]=st; qi[tail]=p-1; q[tail]=head; step[tail]=step[head]+1; } } if(p-3>=1) { ssi=ss; st=sswap(ssi,p,p-3); if(st==sp) { q[++tail]=head; cout<<step[head]+1<<" "; return 0; } if(f[KT(st)]==0) { f[KT(st)]=1; qg[++tail]=st; q[tail]=head; qi[tail]=p-3; step[tail]=step[head]+1; } } if(p+3<=9) { ssi=ss; st=sswap(ssi,p,p+3); if(st==sp) { q[++tail]=head; cout<<step[head]+1<<" "; return 0; } if(f[KT(st)]==0) { f[KT(st)]=1; qg[++tail]=st; q[tail]=head; qi[tail]=p+3; step[tail]=step[head]+1; } } if(p+1<=9&&p!=3&&p!=6) { ssi=ss; st=sswap(ssi,p,p+1); if(st==sp) { q[++tail]=head; cout<<step[head]+1<<" "; return 0; } if(f[KT(st)]==0) { f[KT(st)]=1; qg[++tail]=st; q[tail]=head; qi[tail]=p+1; step[tail]=step[head]+1; } } } } 3.map+双向bfs 8ms #include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; map<string,int>f,step; queue<string>q; string s,t=" 123804765"; int Bfs() { q.push(s);q.push(t); step[s]=0;step[t]=0; f[s]=1;f[t]=2; while(!q.empty()) { string k=q.front();q.pop(); int p=k.find('0'); int ste=step[k]; if(p<7) { string si=k;int pi=p+3; swap(si[p],si[pi]); if(f[si]==0){f[si]=f[k];q.push(si);step[si]=ste+1;} else if(f[si]!=f[k]){return step[si]+ste+1;} } if(p>3) { string si=k;int pi=p-3; swap(si[p],si[pi]); if(f[si]==0){f[si]=f[k];q.push(si);step[si]=ste+1;} else if(f[si]!=f[k]){return step[si]+ste+1;} } if(p!=1&&p!=4&&p!=7) { string si=k;int pi=p-1; swap(si[p],si[pi]); if(f[si]==0){f[si]=f[k];q.push(si);step[si]=ste+1;} else if(f[si]!=f[k]){return step[si]+ste+1;} } if(p!=3&&p!=6&&p!=9) { string si=k;int pi=p+1; swap(si[p],si[pi]); if(f[si]==0){f[si]=f[k];q.push(si);step[si]=ste+1;} else if(f[si]!=f[k]){return step[si]+ste+1;} } } return -1; } int main() { cin>>s;s=" "+s; if(s==t){cout<<0;return 0;} cout<<Bfs(); return 0; }