八数码2

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int INF = (1 << 30);
const LL mod = 1000000007;
const int N = 200001;

string g, seq;

int getpos(string s)
{
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'x') res = i;
    }
    return res;
}

bool complete(string s)
{
    if (s == "12345678x") return true;
    return false;
}

string bfs()
{
    queue<string> q;
    unordered_map<string, string> path;
    unordered_map<string, int> vis;
    q.push(g);
    vis[g] = 1;
    int dx[4] = {-3, -1, 1, 3};
    char c[4] = {'u', 'l', 'r', 'd'};
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int pos = getpos(t);
        for (int i = 0; i < 4; i++)
        {
            string Next = t;
            int x = pos + dx[i];
            if (i == 0 && x < 0) continue;
            if (i == 1 && (x == 2 || x == -1 || x == 5)) continue;
            if (i == 2 && (x == 3 || x == 6 || x == 9)) continue;
            if (i == 3 && x >= 9) continue;
            swap(Next[x], Next[pos]);
            if (vis[Next]) continue;
            vis[Next] = 1;
            path[Next] = path[t] + c[i];
            q.push(Next);
            if (complete(Next)) return path[Next];
        }
    }


    return "";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    while (cin >> c)
    {
        g += c;
        if (c != 'x') seq += c;
    }
    int t = 0;
    for (int i = 0; i < 7; i++) {
        for (int j = i + 1; j < 8; j++)
        {
            if (seq[i] > seq[j]) t++;
        }
    }
    if (t & 1) cout << "unsolvable" << endl;
    else cout << bfs();
}