具体请看注释内容

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

typedef pair<int, string> PIS;
typedef pair<string, char> PSC;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char op[4] = {'u', 'r', 'd', 'l'};

/*
    估值函数（启发式函数）：用来估计当前点到终点的距离，只要保证 <= 最小距离即可！
        ----> 本题使用曼哈顿距离表示！
        估值越接近真实值越好，当估值是0，类似dijkstra！

    A*算法：每次取 优先队列按照起点到当前点的距离 和 当前点到终点的估计值之和排序的最小值！

        除了终点之外，当第一次搜到某个点的时候，距离不一定是最短的，其dist[]的值是不断变小的！
        一个重要性质：只有终点第一次出队时该点是最优解

    证明：终点第一次出队就是最优解！
        反证法：假设终点第一次出队时不是最优解，即dist[end] > dist[end]最优解
                则队列中一定存在最优路径的某一点，记为点 u
                由于估值函数一定 <= 最小距离，因此：dist[end]最优 = dist[u] + dist最优解 >= dist[u] + dist估值
                    ---> dist[end]最优 >= dist[u] + dist估值
                    ？？？ 居然有当前最优解还要最优的最优解！
                    ---> 因此：与假设矛盾，终点第一次出队一定是最优解得证！

    A*应用场景：
        1. 一般用于最小步数模型，即状态数量非常庞大的情况下！
        2. 边权非负
        3. 一定有解的情况（无解会以O(logn)搜完所有状态，比朴素bfs的O(1)要慢）

    BFS && Dijkstra && A* 关系：
        1. dijkstra可以看成是估计距离全部为0的A*算法
        2. BFS入队时判重
        3. Dijkstra出队时判重
        4. A*算法不判重(每一点都会被多次更新)

    关于八数码问题有解的充分必要条件：该状态的逆序对数量为偶数！
        证明：充分性非常复杂！
              必要性证明：左右移动不改变逆序对数量，上下移动会改变：改变情况：-2 0 2 三种情况，因此改变值为偶数！
        推广：可以发现只要判断移动改变的逆序对数量即可得到是否有解，例如十五数码也是同样情况！
*/

// 估计函数（启发式函数）--> 计算曼哈顿距离即可！
int f(string status){
    int res = 0;
    for(int i = 0; i < status.size(); i ++)
        if(status[i] != 'x'){
            int t = status[i] - '1';
            res += abs(t / 3 - i / 3) + abs(t % 3 + i % 3);
        }
    return res;
}

string bfs(string start){

    string end = "12345678x";
    unordered_map<string, int> dist;
    unordered_map<string, PSC> pre;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;

    heap.push({f(start), start});
    dist[start] = 0;

    while(heap.size()){
        auto t = heap.top();
        heap.pop();

        string status = t.second;

        // 只有终点状态出队时才是最小值
        if(status == end) break;

        int k = status.find('x');
        int x = k / 3, y = k % 3;

        string source = status;
        for(int i = 0; i < 4; i ++){
            int tx = x + dx[i], ty = y + dy[i];
            if(tx >= 0 && tx < 3 && ty >= 0 && ty < 3){
                swap(status[k], status[tx * 3 + ty]);

                // A* 算法每个点会被多次更新和入队
                if(!dist.count(status) || dist[status] > dist[source] + 1){
                    dist[status] = dist[source] + 1;
                    pre[status] = {source, op[i]};
                    heap.push({dist[status] + f(status), status});
                }

                swap(status[k], status[tx * 3 + ty]);
            }
        }
    }

    // 路径存储
    string res;
    while(end != start){
        res += pre[end].second;
        end = pre[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}


int main(){
    string start, seq;
    for(int i = 0; i < 9; i ++){
        char c; cin >> c;
        start += c;
        if(c != 'x') seq += c;
    }
    // 逆序对数量统计
    int t = 0;
    for(int i = 0; i < 8; i ++)
        for(int j = i + 1; j < 8; j ++)
            if(seq[i] > seq[j]) t ++;

    if(t & 1) cout << "unsolvable" << endl;
    else cout << bfs(start) << endl;
    return 0;
}