> #include <iostream>
> #include <cstring>
> #define N 362881
> using namespace std;
> int state[N];//为1时正向到达,-1为逆向到达 
> int v[9], step[N];
> const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
> const int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
> struct node
> {
>          int num;
>          int pre;
>          int predir;
>          int nextdir; 
>          int next; 
> }q[N];
> int fabs(int a)
> {
> if(a<0)
> return -a;
> return a; 
> } 
> 
> int canto()//康托展开后面的数全排列 
> {
>          int j, i, tmp;
>          int ans;
>          for (ans = 1, i = 0; i < 9; i++)
>          {
>                  for (tmp = v[i] - 1, j = 0; j < i; j++)  
>                          tmp -= (v[j] < v[i]);
>                  ans = ans + tmp * fact[8 - i];        
>          }
>          return ans;
> }
> 
> 
> 
> void toArray(int num)
> {
>          int i = 8;
>          while (num)
>          {
>          v[i--] = num % 10;
>          num /= 10;
>          }
> }
> 
> int toNum()//将数组换算为数字 
> {
>          int i;
>          int ans = 0;
>          for (i = 0; i < 9; i++)
>             ans =ans*10 + v[i];
>          return ans;
> }
> 
> int BFS()
> {
>          memset(state, false, sizeof(state));
>          int head, tail, val;
>          int xx, xy, i, tx, ty, tmp, pos1, pos2;
>          
>          head = tail = 1;         
>          node p;//开始的状态       
>          p.num = toNum();
>          p.pre = -1;//没有开始值设为-1 
>          p.next=0;//0代表没有意义 
>          p.predir = -1;
>          p.nextdir=0;//0代表无意义 
>          val = canto();
>          state[val] =1;
>          if(123456789==p.num) 
>          return -2;
>          
>                          
>          node last;//最后的状态       
>          last.num=123456789;
>          last.next=-1; 
>          last.pre=0;//0代表无意义 
>          last.predir=0;//0代表无意义 
>          last.nextdir=-1;          
>          q[tail++] = p;
>          q[tail++]=last;
>          state[1] =-2;        
>          while (head < tail)//队列非空 
>          {
>          
>                  p = q[head]; //取出头指针 
>                 // printf("%d\n",p.num);               
>                  toArray(p.num);
>                  val = canto();          
>                  for (i = 0; i < 9; i++)//找到x的位置 
>                      if (v[i] == 9) break;                       
>                  xy = i / 3;
>                  xx = i % 3;          
>                  //move
>                  tx = xx;
>                  ty = xy;
>               for (i = 0; i < 4; i++)
>                  {
>                          tx += move[i][0];
>                          ty += move[i][1];
>                          
>                          if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3)
>                          {
>                                  pos1 = tx + ty * 3;
>                                  pos2 = xx + xy * 3;
>                                  //将值交换 
>                                  tmp = v[pos1];
>                                  v[pos1] = v[pos2];
>                                  v[pos2] = tmp;
>                                  
>                                  val = canto();//计算新值 
>                                  
>                                                                  
>                                                                                                                                  
>                                  if (0==q[head].pre&&0==state[val])//head点逆向到达且没有标记过 
>                                  {
>                                          state[val] =-tail;//标记为逆向到达 
>                                          p.num = toNum();
>                                          p.pre =0;
>                                          p.predir =0;
>                                          p.next=head; 
>                                          p.nextdir=i; 
>                                          q[tail++] = p;
>                                  }
>                                  else if(0==q[head].pre&&state[val]>0)//逆向已到达过 
>                                  {
>                                  q[fabs(state[val])].next=head;
>                                  q[fabs(state[val])].nextdir=i; 
>                                  return fabs(state[val]); 
>                                  } 
>                                  
>                                  else if (0==q[head].next&&0==state[val])//head点正向到达没有标记过 
>                                  {
>                                          state[val] = tail;//标记为以到达过 
>                                          p.num = toNum();
>                                          p.pre =head;
>                                          p.predir =i;
>                                          p.next=0; 
>                                          p.nextdir=0; 
>                                          q[tail++] = p;
>                                  }
>                                  else if(0==q[head].next&&state[val]<0)//head点正向到达新点逆向已到达过 
>                                  {
>                                  q[fabs(state[val])].pre=head;
>                                  q[fabs(state[val])].predir=i; 
>                                  return fabs(state[val]); 
>                                  } 
>                              // printf("p.num=%d p.pre=%d p.pre=%d p.predir=%d p.nextdir=%d\n",p.num,p.pre,p.predir ,p.next, p.nextdir); 
>    
>                                                                 
>                                  tmp = v[pos2];//恢复未移动时的数据 
>                                  v[pos2] = v[pos1];
>                                  v[pos1] = tmp;
>                          }
>                          tx = xx;
>                          ty = xy;
>                  }              
>                                                         
>                  head++;        
>          }
>          
>           return -1;
> }
> 
> void print(int i)
> {
>          int pos = 0;
>          int tempi=i; 
>        //  printf("i=%d\n",i); 
>          // printf("p.num=%d p.pre=%d p.pre=%d p.predir=%d p.nextdir=%d\n",q[i].num,q[i].pre,q[i].predir ,q[i].next, q[i].nextdir); 
>          while (q[i].pre != -1)
>          {
>                  step[pos++] = q[i].predir;
>                  i = q[i].pre;
>          }
>                  
>          for (i = pos - 1; i >= 0; i--)
>          {
>                  switch (step[i])
>                  {
>                  case 0:
>                          cout << 'r';
>                          break;
>                  case 1:
>                          cout << 'd';
>                          break;
>                  case 2:
>                          cout << 'l';
>                          break;
>                  case 3:
>                          cout << 'u';
>                          break;      
>                  }
>          }
>          
>          
>          i=tempi; 
>          while (q[i].next != -1)
>          {
>          if(0==q[i].nextdir) 
>             cout << 'l';
>          else if(1==q[i].nextdir)  
>             cout << 'u';
>          else if(2==q[i].nextdir)  
>             cout << 'r';
>          else if(3==q[i].nextdir)  
>             cout << 'd';   
>                                     
>            i = q[i].next;
>          } 
>          
>          cout<<endl; 
>          }
> int main()
> {       
>          int i;
>          int tmp;
>          char c;
>          for (i = 0; i < 9; i++)
>          {
>                  cin >> c;
>                  if (c == 'x') v[i] = 9;
>                  else v[i] = c - '0';
>          }
> 
>          tmp = BFS();
> 
>          if (-1==tmp ) 
>            cout << "unsolvable"<<endl;
>          else if(-2==tmp)
>            cout<<endl; 
>          else 
>          print(tmp);
>          //system("pause"); 
>          return 0;
> }