1 #include<iostream> 2 #include<string> 3 #include<queue> 4 #include<string.h> 5 using namespace std; 6  7 const int maxn=1000000; 8  9 bool vis[maxn];      //是否被访问过10 string path[maxn];   //记录路径11 int fac[]={          //阶乘12     1,1,2,6,24,120,720,5040,40320,36288013 };14 15 int contor(int s[]){ //康托展开16     int sum=0;17     for(int i=0;i<9;i++){18         int num=0;19         for(int j=i+1;j<9;j++)20             if(s[j] < s[i] )21                 num ++;22         sum += (num * fac[8-i]);23     }24 25     return sum;26 }27 struct node{        //节点28     int s[9];       //记录状态29     int cur;        //记录当前位置30     string path;    //记录路径31 };32 33 queue<node> q;34 int move[4][2]={    //移动方向35     -1,0,1,0,0,-1,0,136 };37 38 char mop[5]="durl"; // 这里的和上面的移动方向相反，是为了反向搜索39 40 void bfs(){41     node no,next;42     for(int i=0;i<8;i++) no.s[i]=i+1; //将起点初始化为目标，进行反向bfs43     no.s[8]=0;no.cur=8;                  44     no.path="";45     q.push(no);46     vis[contor(no.s)]=true;47     path[contor(no.s)]="";48     while(!q.empty()){49         no=q.front();q.pop();50         int x=no.cur/3;51         int y=no.cur%3;52         for(int i=0;i<4;i++){53             int tx=x+move[i][0];54             int ty=y+move[i][1];55             if(tx<0 || tx>2 || ty <0 || ty >2) continue;56             next=no;next.cur=3*tx+ty;57             next.s[no.cur] = no.s[next.cur];58             next.s[next.cur] =0;59             int val=contor(next.s);60             if(!vis[val]){61                 vis[val] =true;62                 next.path=mop[i] + next.path;63                 q.push(next);64                 path[val] = next.path;65             }66         }67     }68 }69 70 71 int main(){72     char ch;73     node no;74     bfs();75     while(cin >> ch){76         if(ch == ‘x‘) {no.s[0] = 0; no.cur=0;}77         else          no.s[0] =ch - ‘0‘;78         for(int i=1;i<9;i++){79             cin>>ch;80             if(ch == ‘x‘){81                 no.s[i] = 0; no.cur=i;82             }else 83                 no.s[i] = ch - ‘0‘;84         }85         int val=contor(no.s);86         if(vis[val]){87             cout<<path[val]<<endl;88         }89         else 90             cout<<"unsolvable"<<endl;91     }92     return 0;93 }