rt，码风良好，对照着OI-WIKI的代码检查的

#include<cstdio>
#include<set>
#include<queue>
#include<algorithm>
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^48);
        ch=getchar();
    }
    return x*w;
}
inline void write(int x) 
{
    if(x<0) 
    { 
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar((x%10)^48);
}
const int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
struct code
{
    int a[5][5];
}start;
bool operator<(const code& x,const code& y)
{
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(x.a[i][j]!=y.a[i][j]) return x.a[i][j]<y.a[i][j];
        }
    }
    return 0;
}
const code goal={{{},{0,1,2,3},{0,8,0,4},{0,7,6,5}}};
struct statu
{
    code x;
    int step;
};
inline int h(code x)
{
    int ans=0;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(x.a[i][j]!=goal.a[i][j]) ans++;
        }
    }
    return ans;
}
bool operator<(const statu& x,const statu& y)
{
    return x.step+h(x.x)<y.step+h(y.x);
}
inline void a_star(code x)
{
    set<code> vis;
    priority_queue<statu> q;
    q.push({x,0});
    while(!q.empty())
    {
        statu u=q.top();
        q.pop();
        /*for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++) write(u.x.a[i][j]);
            putchar('\n');
        }
        putchar('\n');*/
        if(!h(u.x))
        {
            write(u.step);
            return;
        }
        u.step++;
        int zeroi,zeroj;
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                if(u.x.a[i][j]==0) zeroi=i,zeroj=j;
            }
        }
        for(int i=1;i<=4;i++)
        {
            statu v=u;
            int nx=zeroi+dx[i],ny=zeroj+dy[i];
            if(nx<1||nx>3||ny<1||ny>3) continue;
            swap(v.x.a[zeroi][zeroj],v.x.a[nx][ny]);
            if(!vis.count(v.x)) vis.insert(v.x),q.push(v);
        }
    }
}
int main()
{
    int x=read();
    for(int i=3;i>=1;i--)
    {
        for(int j=3;j>=1;j--)
        {
            start.a[i][j]=x%10;
            x/=10;
        }
    }
    a_star(start);
    return 0;
}