题解 | #八数码#

核心思路：
bfs+康托展开去重
关于康托展开：
康托展开的公式如下：k=a[n](n-1)!+a[n-1](n-2)!+....+a[1]0!;
康托展开主要解决的是全排列的状态储藏问题，k指的是当前这个数在全排列中由小到大排第k个。
其中的a[n]指的是当前这个数位上的数字在还没出现的数字中比他小的数有几个；
例如<1. 2. 3. 4>
<2134>
他的k=1*3!+0 *2!+0*1!+0 *0!;
所以我们就可以利用康托展开来记录这个状态有没有走过。避免再走一遍。

表达能力有限可自行学习康托展开

个人觉得康托展开好强，觉得不是人能想出来的，可是就是有人能自己推出来，呜呜呜呜
康托展开的代码贴上

bool contuo(int p[])
{

    long rest=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++){
            if(p[i]>p[j])cnt++;
        }
        rest+=cnt*=jie[9-i-1];
    }
}

利用结构体可存每一步是怎么走的（可能空间会有点大，但是a了这道题）
udlr的优先级并不影响，只要长度一样就大胆的提交；
贴上ac代码

#include<bits/stdc++.h>
#include<queue>
#include<string>
#include<vector>
using namespace std;
struct node{
    int a[10];
string b;
};
bool contuo(int p[]);
int xx[4]={-1,0,1,0};
int yy[4]={0,-1,0,1};
bool vis[1000000];
int ans[10]={1,2,3,4,5,6,7,8,0};
int jie[10]={1,1,2,6,24,120,720,5040,40320,362880};//预处理后面方便直接用
int start[10];
queue <node> s;
bool check(int o[])
{
    for(int i=0;i<9;i++){
        if(o[i]!=ans[i])return false;
    }    
    return true;
}
string bfs(void)
{
    node e;
    for(int i=0;i<9;i++)
    e.a[i]=start[i];
    s.push(e);
    while(!s.empty())
    {    
        e=s.front();
        s.pop();
        if(check(e.a)){
            return e.b;
        }
        int z;
        for(z=0;z<9;z++)
        if(e.a[z]==0)break;
        int x1=z/3;
        int y1=z%3;
        for(int i=0;i<4;i++){
            int nx=x1+xx[i];
            int ny=y1+yy[i];
            int nz=nx*3+ny;
            node ne;
            if(ny>=0&&nx>=0&&ny<3&&nx<3)
            {
                ne=e;
                swap(ne.a[z],ne.a[nz]);
                if(contuo(ne.a))
                {
                    if(xx[i]==-1)ne.b.insert(ne.b.end(),'u');//利用string的性质，在后面直接插入这一步的操作
                    if(xx[i]==1)ne.b.insert(ne.b.end(),'d');
                    if(yy[i]==1)ne.b.insert(ne.b.end(),'r');
                    if(yy[i]==-1)ne.b.insert(ne.b.end(),'l');
                    s.push(ne);
                }
            }
        }
    }    
    return "unsolvable";
}

bool contuo(int p[])
{

    long rest=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++){
            if(p[i]>p[j])cnt++;
        }
        rest+=cnt*=jie[9-i-1];
    }

    if(!vis[rest]){
        vis[rest]=true;
        return true;
    }
return false;
}
int main(){
    char a1;
    for(int i=0;i<9;i++)
    {
        scanf(" %c",&a1);
        if(a1=='x')start[i]=0;
        else start[i]=a1-'0';
    }

    string m=bfs();
    cout<<m<<endl;
    return 0;
}