97分???

#include <bits/stdc++.h>
using namespace std;
#define int long long
string ss,t="123804765";
map<string,int> vis;
int di[5]={-1,1,-3,3};
int h(string s)
{
    int cnt=0;
    for(int i=0;i<=8;i++) if(s[i]!=t[i]) cnt++;
    return cnt;
}
struct dot
{
    string s;
    int step;
    friend bool operator<(const dot &a,const dot&b)
    {
        return a.step+h(a.s)>b.step+h(b.s);
    }
};
priority_queue<dot> que;
signed main()
{
    cin>>ss;
    que.push({ss,0});
    vis[ss]=1;
    while(!que.empty())
    {
        dot hd=que.top();
        que.pop();
        if(hd.s==t)
        {
            cout<<hd.step;
            return 0;
        }
        int dir;
        for(int i=0;i<=8;i++)
        {
            if(hd.s[i]=='0') dir=i;
        }
        for(int i=0;i<4;i++)
        {
            if(di[i]==1&&dir%3==2) continue;
            if(di[i]==-1&&dir%3==0) continue;
            int ii=di[i]+dir;
            if(ii<0||ii>8) continue;
            string ns=hd.s;
            swap(ns[dir],ns[ii]);
            if(vis[ns]==1) continue;
            vis[ns]=1;
            que.push({ns,hd.step+1});
        }
    }
    cout<<0;
    return 0;
}