广搜

#include <bits/stdc++.h>
using namespace std;
const int ed = 123804765;
map<int, int> dis;
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int st;
    cin >> st;
    q.push(st);
    dis[st] = 1;
    while (!q.empty() && dis[ed] == 0)
    {
        int now = q.front();
        q.pop();
        /*
            d[0][0] d[0][1] d[0][2]
            d[1][0] d[1][1] d[1][2]
            d[2][0] d[2][1] d[2][2]
        */
        int d[3][3];
        d[0][0] = now / 100000000 % 10;
        d[0][1] = now / 10000000 % 10;
        d[0][2] = now / 1000000 % 10;
        d[1][0] = now / 100000 % 10;
        d[1][1] = now / 10000 % 10;
        d[1][2] = now / 1000 % 10;
        d[2][0] = now / 100 % 10;
        d[2][1] = now / 10 % 10;
        d[2][2] = now / 1 % 10;
        int x, y;
        for (int i = 0; i <= 2; i++)
            for (int j = 0; j <= 2; j++)
                if (d[i][j] == 0)
                    x = i, y = j;
        if (x != 0)
        {
            swap(d[x][y], d[x - 1][y]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x - 1][y]);
        }
        if (x != 2)
        {
            swap(d[x][y], d[x + 1][y]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x + 1][y]);
        }
        if (y != 0)
        {
            swap(d[x][y], d[x][y - 1]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x][y - 1]);
        }
        if (y != 2)
        {
            swap(d[x][y], d[x][y + 1]);
            int nxt = 0;
            for (int i = 0; i <= 2; i++)
                for (int j = 0; j <= 2; j++)
                    nxt = nxt * 10 + d[i][j];
            if (dis[nxt] == 0)
            {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
            }
            swap(d[x][y], d[x][y + 1]);
        }
    }
    cout << dis[ed] - 1;
    return 0;
}