#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;
}

• Re:双向搜索0MS YES (8134) xrxdhy 2015-05-17 23:25:48
• Re:双向搜索0MS YES (8134) dacc 2016-03-23 15:33:57