样本输入
2 3 4 1 5 x 7 6 8
样本输出
ullddrurdllurdruldr #include<iostream> #include<algorithm> #include<fstream> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<cmath> #include<cctype> #include<vector> #include<limits.h> #include<queue> using namespace std; const int maxn=1e5; //大于9！即可 int mov[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; char mo[5]="udlr"; int vis[maxn]; char path[maxn]; int fac[10]; struct mmp { char s[10]; //存八数码 int pos; //0号字符所在的位置 int par; //上一个状态的编号 char mv; //向哪儿移动 //mmp(char si[10],int pp,int aa,char mm):s(si),pos(pp),par(aa),mv(mm){} }; mmp q1[maxn]; mmp m1,m2; void cal() //求阶乘的 { fac[0]=1; for(int i=1; i<10; ++i) { fac[i]=i*fac[i-1]; } } int kangtuo(char sd[]) //求数组s排列在全排列中第几大，从1开始 { int i,j,ans,num=0; int sum=9; for(i=0; i<sum; ++i) { for(j=i+1,ans=0; j<sum; ++j) { if(sd[j]<sd[i]) ans++; } num+=ans*fac[sum-i-1]; } return num+1; } void print(mmp m3) //根据每个结构体中存的父节点遍历 { int i=0,j; while(m3.par!=-1) { path[i++]=m3.mv; m3=q1[m3.par]; } for(j=i-1; j>=0; j--) cout<<path[j]; cout<<endl; } int bfs() { int a,b,x,y,i,head=0,tail=1; m1.par=-1; m1.mv='0'; q1[0]=m1; a=kangtuo(m1.s); vis[a]=1; while(head!=tail) { m1=q1[head]; if(strcmp(q1[head].s,"123456780")==0) { print(m1); return 1; } for(i=0; i<4; ++i) { x=m1.pos/3+mov[i][0]; y=m1.pos%3+mov[i][1]; if(x<0||y<0||x>2||y>2) continue; m2=m1; m2.par=head; m2.mv=mo[i]; m2.pos=x*3+y; //新的空位 m2.s[m1.pos]=m1.s[m2.pos]; //交换位置 m2.s[m2.pos]='0'; b=kangtuo(m2.s); if(vis[b]==0) { vis[b]=1; q1[tail++]=m2; } } head++; } return 0; } int main() { cal(); int i; char p[10]; for(i=0; i<9; ++i) { scanf("%s",p); if(p[0]=='x') { m1.pos=i; m1.s[i]='0'; } else m1.s[i]=p[0]; } if(bfs()==0) cout<<"unsolvable"<<endl; return 0; }
