八数码（A* + 康托展开）

题目让我们求出将八数码复原的最小步数并且输出出具体方案，这是一道搜索题，因为数据范围很小。但是这道题可以借助两个算是比较高级的知识来优化，A* 算法和康托展开，A*是因为加入评估函数后可以大大的加快搜索速度。这道题的评估函数便是每个数当前所在位置和那个数最终所在位置的曼哈顿距离总和。而这里因为棋盘上的每个状态不是像一般的问题那样是某个点或是某个数，而是一个全排列的不同排列方式，不太容易记录每个状态，当然可以用普通的哈希去做，但是因为这里是全排列的缘故，所以借助康托展开和逆康托展开是十分适合这道题的，效率上是线性的，因此时间上也是会更占优。

// Author: Feng
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
int head[1000010], Edge_Num;
struct Edge { int to, next; ll w; }e[2000010];
inline void ade(int x, int y, ll w) { e[++Edge_Num] = { y,head[x],w }; head[x] = Edge_Num; }
inline void G_init(int n) { memset(head, 0, sizeof(int) * (n + 100)); Edge_Num = 0; }
int dir[8][2] = { {-1,0},{0,-1},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1} };
const long double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return f == 1 ? x : -x;
}
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const int M = 5e6 + 10;
const int N = 5e5 + 10;
int fac[12];
int n = 9;
inline string inv_kantuo(int x) {//逆康托展开，建立一个数到一个全排列的映射
    string res = "";
    x--;
    vector<char>vec;
    for (int i = 1; i <= n; i++)vec.pb(i + '0');
    for (int i = 1; i <= n; i++) {
        int t = x / fac[n - i];
        x %= fac[n - i];
        res += vec[t];
        vec.erase(vec.begin() + t);
    }
    return res;
}
string an = "uldr";
inline int kangtuo(string state) {//康托展开，建立一个全排列到一个数的映射
    int res = 1;
    int len = state.length();
    for (int i = 0; i < len; i++) {
        int cnt = 0;
        for (int j = i + 1; j < len; j++) {
            if (state[i] > state[j])++cnt;
        }
        res += cnt * fac[len - i - 1];
    }
    return res;
}
int ed;
inline int dis(int x, int y) {
    int fx = x / 3, fy = x % 3;
    int gx = y / 3, gy = y % 3;
    return abs(fx - gx) + abs(fy - gy);
}
inline int f(int x) {
    string s = inv_kantuo(x);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += dis(i, s[i] - '0' - 1);
    }
    return ans;
}
inline pii gao(string s) {
    int p = 0;
    pii ans;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (s[p++] == '9')ans.X = i, ans.Y = j;
        }
    }
    return ans;
}
inline bool check(int x,int y) {
    return x >= 1 && x <= 3 && y >= 1 && y <= 3;
}
struct La {
    int pre, di;
}last[N];
inline int pos(int x, int y) {
    x--, y--;
    return x * 3 + y;
}
int Dis[N];
struct MM {
    int state, cost;
    bool friend operator<(const MM& m1, const MM& m2) {
        return m1.cost > m2.cost;
    }
};
priority_queue<MM>q;
bool vis[N];
bool A_star(int st) {
    q.push({ st,f(st) });
    memset(Dis, inf, sizeof Dis);
    memset(vis, 0, sizeof vis);
    Dis[st] = 0;
    while (q.size()) {
        MM now = q.top(); q.pop();
        if (now.state == 1) return 1;
        if (vis[now.state])continue;
        vis[now.state] = 1;
        string sta = inv_kantuo(now.state);
        pii ex = gao(sta);
        for (int i = 0; i < 4; i++) {
            pii ed = ex;
            ed.X += dir[i][0], ed.Y += dir[i][1];
            if (!check(ed.X, ed.Y))continue;
            string g = sta;
            swap(g[pos(ex.X, ex.Y)], g[pos(ed.X, ed.Y)]);
            int gg = kangtuo(g);
            if (Dis[gg] > Dis[now.state] + 1) {
                Dis[gg] = Dis[now.state] + 1;
                last[gg].pre = now.state;
                last[gg].di = i;
                q.push({ gg,Dis[gg] + f(gg) });
            }
        }
    }
    return 0;
}
void solve() {
    string start = "", temp;
    for (int i = 0; i < 9; i++) {
        cin >> temp;
        if (temp == "x")temp = "9";
        start += temp;
    }
    int sta = kangtuo(start);
    if (!A_star(sta)) {
        puts("unsolvable");
    }
    else {
        string ans = "";
        ed = 1;
        while (ed != sta) {
            ans += an[last[ed].di];
            ed = last[ed].pre;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
}
int p[20];
int main() {
    fac[0] = 1;
    for (int i = 1; i <= 9; i++)fac[i] = fac[i - 1] * i;
    //for (int i = 1; i <= 9; i++)p[i] = i;
    //do {
    //    string s = "";
    //    for (int i = 1; i <= 9; i++) {
    //        s += '0' + p[i];
    //    }
    //    cout << s << endl;
    //    int x = kangtuo(s);
    //    cout << x << endl;
    //    cout << inv_kantuo(x) << endl;
    //    cout << endl;
    //} while (next_permutation(p + 1, p + 1 + 9));
    int _T = 1;
    while (_T--) solve();
}