#include <bits/stdc++.h>
using namespace std;
map<string, int> vis;
map<string, int> color;
const string mb = "123804765";
string inp;
queue<string> qf, qb;
queue<int> stepf, stepb;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
string x;
int main(void)
{
    cin >> inp;
    if (inp == mb)
    {
        cout << 0;
        return 0;
    }
    qf.push(inp);
    qb.push(mb);
    color[inp] = 1
    color[mb] = 2;
    vis[inp] = 0;
    vis[mb] = 1;
    stepf.push(0);
    stepb.push(1);
    while (!qf.empty() || !qb.empty())
    {
        int st = stepf.front();
        string s = qf.front();
        if (!qf.empty())
        {
            int y[5][5];
            int sum = -1;
            int ox, oy;
            for (int i = 1; i <= 3; i++)
            {
                for (int j = 1; j <= 3; j++)
                {
                    sum++;
                    y[i][j] = s[sum] - '0';
                    if (y[i][j] == 0)
                    {
                        ox = i;
                        oy = j;
                    }
                }
            }
            for (int i = 0; i < 4; i++)
            {
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                swap(y[ox][oy], y[nx][ny]);
                x = "";
                for (int i = 1; i <= 3; i++)
                {
                    for (int j = 1; j <= 3; j++)
                    {
                        x += y[i][j] + '0';
                    }
                }
                swap(y[ox][oy], y[nx][ny]);
                if (color[x] == 2)
                {
                    cout << st + vis[x];
                    return 0;
                }
                if (color[x] == 1)
                    continue;
                vis[x] = st + 1;
                color[x] = 1;
                qf.push(x);
                stepf.push(st + 1);
            }
            qf.pop();
            stepf.pop();
        }
        st = stepb.front();
        s = qb.front();
        if (!qb.empty())
        {
            int y[5][5];
            int sum = -1;
            int ox, oy;
            for (int i = 1; i <= 3; i++)
            {
                for (int j = 1; j <= 3; j++)
                {
                    sum++;
                    y[i][j] = s[sum] - '0';
                    if (y[i][j] == 0)
                    {
                        ox = i;
                        oy = j;
                    }
                }
            }
            for (int i = 0; i < 4; i++)
            {
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                swap(y[ox][oy], y[nx][ny]);
                x = "";
                for (int i = 1; i <= 3; i++)
                {
                    for (int j = 1; j <= 3; j++)
                    {
                        x += y[i][j] + '0';
                    }
                }
                swap(y[ox][oy], y[nx][ny]);
                if (color[x] == 1)
                {
                    cout << st + vis[x];
                    return 0;
                }
                if (color[x] == 2)
                    continue;
                vis[x] = st + 1;
                color[x] = 2;
                qb.push(x);
                stepb.push(st + 1);
            }
            qb.pop();
            stepb.pop();
        }
    }
    return 0;
}

我在除了$AC$就是$TLE$的$BFS$代码上改成双向$BFS$为啥还$WA$了(*…*呜咕）