rt，用的双向BFS

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*w;
}
inline void write(int x) 
{
    if(x<0) 
    { 
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
struct statu
{
    string x;
    int step; 
};
struct swapchar
{
    int x,y;
};
bool operator<(const statu& a,const statu& b)
{
    return a.x<b.x;
}
int dx[]={-1,-3,1,3};
inline void bfs(string b,string e)
{
    map<statu,int> vis;
    queue<statu> q;
    q.push(statu{b,0});
    q.push(statu{e,0});
    vis[statu{b,0}]=1;
    vis[statu{e,0}]=2;
    while(!q.empty())
    {
        statu now=q.front();
        q.pop();
        vector<swapchar> newstatus; 
        for(int i=0;i<9;i++)
        {
            for(auto j:dx)
            {
                swapchar newstatu=swapchar{i,i+j};
                if(newstatu.x>=0&&newstatu.x<9&&newstatu.y>=0&&newstatu.y<9) newstatus.push_back(newstatu);
            }
        }
        for(auto i:newstatus)
        {
            statu tmp;
            tmp.x=now.x;
            swap(tmp.x[i.x],tmp.x[i.y]);
            tmp.step=now.step+1;
            if(tmp.x==e)
            {
                write(now.step+tmp.step+1);
                putchar('\n');
                return;
            }
            if(vis[now]==1)
            {
                vis[tmp]=1;
                q.push(tmp);
            }
            if(vis[now]==2)
            {
                vis[tmp]=2;
                q.push(tmp);
            }
        }
    }
}
int main()
{
	string s;
    cin>>s;
    bfs(s,"123804765");
	return 0;
}