这道题花了我一晚上去了看了一种解法，结果最后悲剧了，只在poj上过了，在hdu上TLE，原因是因为hdu上是多组数

据，而poj上是一组数据。。。悲剧啊，学的方法有点低效。。。

不过那个打印路径方法倒是可以借鉴一下，从终点往起点递归，打印路径。。。

贴代码：

?

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define N 370000 int first[9]; int last[9] = {1,2,3,4,5,6,7,8,0}; int f[9]; int visit[N]; int p[N][9];//保存状态的数组 int dist[N];//记录路径 const int dx[] = {-1,0,0,1}; const int dy[] = {0,-1,1,0}; char dir[4] = {'d','r','l','u'}; void init()//好像是一个叫做康托展开的神马东东 { f[0] = 1; for(int i=1; i<10; i++) f[i] = f[i-1] * i; } int hash1(int *a)//这个是求该数字0-9在全排列中的第几个数，用来判重 { int i,j; int s = 0; for(i=0; i<9; i++) { int cnt = 0; for(j=i+1; j<9; j++) { if(a[j] < a[i]) cnt++; } s += f[8-i] * cnt; } return s; } int bfs(int fir,int las) { int i,cur; memset(visit,0,sizeof(visit)); memset(dist,0,sizeof(dist)); memset(p,0,sizeof(p)); visit[fir] = 1; dist[fir] = 0; for(i=0; i<9; i++) p[fir][i] = first[i]; queue
      
       que; que.push(fir); while(!que.empty()) { int temp = que.front(); que.pop(); if(temp == las) return dist[las]; for(cur=0; cur<9; cur++) { if(p[temp][cur] == 0) break; } int x = cur/3; int y = cur%3; int change[9]; for(i=0; i<4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if(( xx>=0 ) && ( yy>=0 ) && (xx < 3) && (yy < 3)) { memcpy(change,p[temp],sizeof(change)); change[cur] = p[temp][xx*3+yy]; change[xx*3+yy] = 0; int change1 = hash1(change); if(visit[change1] == 0) { visit[change1] = 1; dist[change1] = dist[temp] + 1; que.push(change1); memcpy(p[change1],change,sizeof(change)); } } } } return -1; } void print_path(int fir,int las)//从终点递归打印路径 { if(las == fir) return; int cur; int change[9]; for(cur=0; cur<9; cur++) { if(p[las][cur] == 0) break; } int x = cur/3; int y = cur%3; for(int i=0; i<4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if(( xx>=0 ) && ( yy>=0 ) && (xx < 3) && (yy < 3)) { memcpy(change,p[las],sizeof(change)); change[cur] = p[las][xx*3+yy]; change[xx*3+yy] = 0; int change1 = hash1(change); if((dist[las] == dist[change1] +1) && visit[change1]) { print_path(fir, change1); printf(%c,dir[i]); break; } } } return ; } int main() { init(); int i,k = 0; char a[30]; while(gets(a)) { //getchar(); k = 0; int len = strlen(a); for(i=0; i
       
        = '1') && (a[i] <= '8')) first[k++] = a[i] - '0'; else if(a[i] == 'x') first[k++] = 0; } //for(i=0; i<9; i++) // printf(%d ,first[i]); puts(); int fir = hash1(first);//找出某一序列所对应的全排列的位次 int las = hash1(last); int ans = bfs(fir,las); // printf(%d ,ans); if(ans < 0) printf(unsolvable); else print_path(fir,las); puts(); } return 0; } 
       
      
     
    
   
  

?

?