题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

思路：

由于自己对康拓展开用的太少，看到这个题没想到康拓展开，最开始打算直接转换为数字，但太占内存了，又想到可以将状态存进set，后来查了一下发现原来是考察康拓展开。另外就是需要打表预处理，这样快很多。BFS部分就是已知终点，从终点逆向搜索，并存每个状态的上一个状态以及操作，以便输出。

坑点：输入是多组输入，POJ那道题才是一组输入，卡在这一上午T_T。

　　　有一组输入为12345678x，需要特殊处理，不能不输出，可以输出“lr”。

1 #include
     
       2 using namespace std; 3  4 const int maxn=1e6+5; 5 struct node{ 6     char a[9]; 7     int x,y; 8     int cnt; 9 }tmp;10 11 int fac[9];12 int vis[maxn];13 char path[maxn];14 int pre[maxn];15 int go[4][2]={-1,0,0,1,1,0,0,-1};16 17 void init(){18     fac[0]=fac[1]=1;19     for(int i=2;i<9;i++) fac[i]=fac[i-1]*i;20 }21 22 int cantour(char *s){23     int ans=0,k;24     for(int i=0;i<8;i++){25         k=0;26         for(int j=i+1;j<9;j++)27             if(s[j]
      
        q;35     for(int i=0;i<8;i++)36         tmp.a[i]=i+1+'0';37     tmp.a[8]='0';38     tmp.x=2,tmp.y=2,tmp.cnt=cantour(tmp.a);39     vis[tmp.cnt]=1;40     q.push(tmp);41     path[tmp.cnt]=-1;42     while(!q.empty()){43         node now=q.front();q.pop();44         int nx=now.x,ny=now.y,ncnt=now.cnt;45         for(int i=0;i<4;i++){46             int xx=nx+go[i][0],yy=ny+go[i][1];47             if(xx<0||xx>2||yy<0||yy>2) continue;48             strcpy(tmp.a,now.a);49             swap(tmp.a[nx*3+ny],tmp.a[xx*3+yy]);50             tmp.x=xx,tmp.y=yy,tmp.cnt=cantour(tmp.a);51             if(!vis[tmp.cnt]){52                 vis[tmp.cnt]=1;53                 pre[tmp.cnt]=ncnt;54                 if(i==0) path[tmp.cnt]='d';55                 else if(i==1) path[tmp.cnt]='l';56                 else if(i==2) path[tmp.cnt]='u';57                 else path[tmp.cnt]='r';58                 q.push(tmp);59             }60         }61     }62 }63 64 void print(int f){65     while(path[f]!=-1){66         printf("%c",path[f]);67         f=pre[f];68     }69     printf("\n");70 }71 72 int main(){73     char c[9],ch;74     int f;75     init();76     bfs();77     while(scanf(" %c",&ch)!=EOF){78         if(ch=='x') c[0]='0';79         else c[0]=ch;80         for(int i=1;i<9;i++){81             scanf(" %c",&ch);82             if(ch=='x') c[i]='0';83             else c[i]=ch;84         }85         f=cantour(c);86         if(path[f]==-1) printf("lr\n");87         else if(!vis[f]) printf("unsolvable\n");88         else print(f);89     }90     return 0;91 }