八数码1

#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 = 3;

int idx;
char g[N][N];

struct Row{
    char a, b, c;
};

struct State{
    Row first, second, third;
    int x, y;
    string path;
};

bool check(int x, int y)
{
    if (x < 0 || x >= 3 || y < 0 || y >= 3) return false;
    return true;
}

bool complete(State Next)
{
    if (Next.first.a == '1' && Next.first.b == '2' && Next.first.c == '3' && 
    Next.second.a == '4' && Next.second.b == '5' && Next.second.c == '6' &&
    Next.third.a == '7' && Next.third.b == '8' && Next.third.c == 'x') return true;
    else return false;
}
    

string bfs(State start)
{
    queue<State> q;
    q.push(start);
    unordered_map<string, int> vis;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    while (q.size())
    {
        idx++;
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = t.x + dx[i], y = t.y + dy[i]; // 新坐标
            if (!check(x, y)) continue;
            string ck = "";
            State Next = {t.first, t.second, t.third, x, y, t.path}; //新状态
            string newpath = t.path; // 新路径

            char p[3][3]; // 临时地图
            p[0][0] = Next.first.a, p[0][1] = Next.first.b, p[0][2] = Next.first.c;
            p[1][0] = Next.second.a, p[1][1] = Next.second.b, p[1][2] = Next.second.c;
            p[2][0] = Next.third.a, p[2][1] = Next.third.b, p[2][2] = Next.third.c;

            if (i == 0) // 下
            {
                newpath += 'd';
                Next.path = newpath;
                swap(p[x][y], p[x - 1][y]);
                Next.first = {p[0][0], p[0][1], p[0][2]};
                Next.second = {p[1][0], p[1][1], p[1][2]};
                Next.third = {p[2][0], p[2][1], p[2][2]};
                ck += Next.first.a;
                ck += Next.first.b;
                ck += Next.first.c;
                ck += Next.second.a;
                ck += Next.second.b;
                ck += Next.second.c;
                ck += Next.third.a;
                ck += Next.third.b;
                ck += Next.third.c;
                if (vis[ck]) continue;
                vis[ck] = 1;
                q.push(Next);
            }
            else if (i == 1) // 右
            {
                newpath += 'r';
                Next.path = newpath;
                swap(p[x][y], p[x][y - 1]);
                Next.first = {p[0][0], p[0][1], p[0][2]};
                Next.second = {p[1][0], p[1][1], p[1][2]};
                Next.third = {p[2][0], p[2][1], p[2][2]};
                ck += Next.first.a;
                ck += Next.first.b;
                ck += Next.first.c;
                ck += Next.second.a;
                ck += Next.second.b;
                ck += Next.second.c;
                ck += Next.third.a;
                ck += Next.third.b;
                ck += Next.third.c;
                if (vis[ck]) continue;
                vis[ck] = 1;
                q.push(Next);
            }
            else if (i == 2) // 上
            {
                newpath += 'u';
                Next.path = newpath;
                swap(p[x][y], p[x + 1][y]);
                Next.first = {p[0][0], p[0][1], p[0][2]};
                Next.second = {p[1][0], p[1][1], p[1][2]};
                Next.third = {p[2][0], p[2][1], p[2][2]};
                ck += Next.first.a;
                ck += Next.first.b;
                ck += Next.first.c;
                ck += Next.second.a;
                ck += Next.second.b;
                ck += Next.second.c;
                ck += Next.third.a;
                ck += Next.third.b;
                ck += Next.third.c;
                if (vis[ck]) continue;
                vis[ck] = 1;
                q.push(Next);
            }
            else // 左
            {
                newpath += 'l';
                Next.path = newpath;
                swap(p[x][y], p[x][y + 1]);
                Next.first = {p[0][0], p[0][1], p[0][2]};
                Next.second = {p[1][0], p[1][1], p[1][2]};
                Next.third = {p[2][0], p[2][1], p[2][2]};
                ck += Next.first.a;
                ck += Next.first.b;
                ck += Next.first.c;
                ck += Next.second.a;
                ck += Next.second.b;
                ck += Next.second.c;
                ck += Next.third.a;
                ck += Next.third.b;
                ck += Next.third.c;
                if (vis[ck]) continue;
                vis[ck] = 1;
                q.push(Next);
            }
            if (complete(Next))
            {
                return Next.path;
            }
        }
    }
    return "No";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> g[i][j];
        }
    }
    int x, y;
    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++){
            if (g[i][j] == 'x')
            {
                x = i, y = j;
            }
        }
    }
    Row r1 = {g[0][0], g[0][1], g[0][2]};
    Row r2 = {g[1][0], g[1][1], g[1][2]};
    Row r3 = {g[2][0], g[2][1], g[2][2]};
    State start = {r1, r2, r3, x, y, ""};
    string seq = "";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++){
            if (g[i][j] != 'x') seq+=g[i][j];
        }
    }
    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 % 2 == 1) {
        cout << "unsolvable" << endl;
    }
    else cout << bfs(start);
}