bfs,每个状态用康托展开来记录,用pre来记录上一个状态和避免重复搜索,顺便把方向记录在dir里,最后倒叙输出.

康托展开:得到某一排列是全排列从小到大的第几个,可以用来记录组合状态.

参考的:http://hi.baidu.com/mk%B5%C4%B4%B8%D7%D3/blog/item/4db13a16d7f4b00f4a90a7b7.html

#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
int fac[10];
int pre[400000];
char dir[400000];
void init()
{
    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
}

long cantor(int s[])
{
    int i,j,t;
    long num=0;
    for(i=0;i<9-1;i++)
    {
        t=0;
        for(j=i+1;j<9;j++)
            if(s[j]<s[i]) ++t;
        num+=fac[9-i-1]*t;
    }
    return num;
}
 
void uncantor(int s[],int ct)
{
    int i,j,t,r;
    bool p[10]={0};
    for(i=0;i<9;i++)
    {
        t=ct/fac[9-i-1]+1;
        ct%=fac[9-i-1];
        r=0,j=1;
        while(1)
        {
            if(!p[j]) r++;
            if(r==t) break;
            j++;
        }
        s[i]=j;p[j]=1;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    init();
    int tc[9];char c[2];
    int ot,t,i;bool ok=0;
    for(i=0;i<9;i++)
    {
        scanf("%s",c);
        if(c[0]=='x') tc[i]=9;
        else tc[i]=c[0]-'0';
    }

    memset(pre,0,sizeof(pre));
    queue<int> q;
    t=cantor(tc);pre[t]=-1;q.push(t);
    while(!q.empty())
    {
        ot=q.front();q.pop();
        if(ot==0) {ok=1;break;}

        uncantor(tc,ot);
        for(i=0;i<9;i++) if(tc[i]==9) break;
        //u
        if(i!=0&&i!=1&&i!=2)
        {
            swap(tc[i],tc[i-3]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='u';q.push(t);}
            swap(tc[i],tc[i-3]);
        }
        //d
        if(i!=6&&i!=7&&i!=8)
        {
            swap(tc[i],tc[i+3]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='d';q.push(t);}
            swap(tc[i],tc[i+3]);
        }
        //l
        if(i!=0&&i!=3&&i!=6)
        {
            swap(tc[i],tc[i-1]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='l';q.push(t);}
            swap(tc[i],tc[i-1]);
        }
        //r
        if(i!=2&&i!=5&&i!=8)
        {
            swap(tc[i],tc[i+1]);
            t=cantor(tc);
            if(!pre[t]) {pre[t]=ot;dir[t]='r';q.push(t);}
            swap(tc[i],tc[i+1]);
        }
    }
    if(ok)
    {
        stack<char> s;
        while(pre[ot]!=-1)
        {
            s.push(dir[ot]);
            ot=pre[ot];
        }
        while(!s.empty())
        {printf("%c",s.top());s.pop();}
    }
    else printf("unsolvable");
    return 0;
}