[AcWing 179] 八数码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,string> PIS;

const int N = 1e6 + 10;

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

int f(string s)
{
    int res = 0;
    for (int i = 0; i < s.size(); i ++)
        if (s[i] != 'x') {
            int t = s[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}

string bfs()
{
    string end = "12345678x";
    unordered_map<string, int> d;
    unordered_map<string, pair<string,char>> pre;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
    
    heap.push({f(start), start});
    d[start] = 0;

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        string s = t.second;
        if (s == end)
            break;
        int step = d[s];
        int p = s.find('x');
        int x = p / 3, y = p % 3;
        string pre_s = s;
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= 3 || b < 0 || b >= 3)
                continue;
            swap(s[x * 3 + y], s[a * 3 + b]);
            if (!d.count(s) || d[s] > step + 1) {
                d[s] = step + 1;
                pre[s] = {pre_s, op[i]};
                heap.push({d[s] + f(s), s});
            }
            swap(s[x * 3 + y], s[a * 3 + b]);
        }
    }
    string res;
    while (end != start) {
        res += pre[end].second;
        end = pre[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

void solve()
{
    char c;
    while (cin >> c) {
        start += c;
    }
    int t = 0;
    for (int i = 0; i < start.size(); i ++)
        for (int j = i + 1; j < start.size(); j ++) {
            int s1 = start[i], s2 = start[j];
            if (s1 == 'x' || s2 == 'x')
                continue;
            if (s1 > s2)
                t ++;
        }
    if (t % 2)
        cout << "unsolvable" << endl;
    else
        cout << bfs() << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}