没什么好说的，dfs过掉
#include<iostream>
#include<cstring>
using namespace std;
string st,op;
int dep;
int hf(string st){
int ans=0;
for(register int i=0;i<st.size();++i){
if(st[i]=='0')continue;
int k=op.find(st[i]),r=i/3,c=i%3;
int x=k/3,y=k%3;
ans+=abs(r-x)+abs(c-y);
}
return ans;
}
const int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
bool dfs(int now, int pre){
int cnt=hf(st);
if(!cnt)return 1;
if(now+cnt>dep)return 0;
int pos=st.find('0'),x=pos/3,y=pos%3;
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>2||ny<0||ny>2||3*nx+ny==pre)
continue;
swap(st[pos],st[3*nx+ny]);
if(dfs(now+1,pos))
return 1;
swap(st[pos],st[3*nx+ny]);
}
return 0;
}
int main(){
cin>>st;
op="123804765";
dep=hf(st);
while(!dfs(0,-1)&&dep<=27)
++dep;
cout<<dep<<endl;
return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
string st,op;
int dep;
int hf(string st){
int ans=0;
for(register int i=0;i<st.size();++i){
if(st[i]=='0')continue;
int k=op.find(st[i]),r=i/3,c=i%3;
int x=k/3,y=k%3;
ans+=abs(r-x)+abs(c-y);
}
return ans;
}
const int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
bool dfs(int now, int pre){
int cnt=hf(st);
if(!cnt)return 1;
if(now+cnt>dep)return 0;
int pos=st.find('0'),x=pos/3,y=pos%3;
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>2||ny<0||ny>2||3*nx+ny==pre)
continue;
swap(st[pos],st[3*nx+ny]);
if(dfs(now+1,pos))
return 1;
swap(st[pos],st[3*nx+ny]);
}
return 0;
}
int main(){
cin>>st;
op="123804765";
dep=hf(st);
while(!dfs(0,-1)&&dep<=27)
++dep;
cout<<dep<<endl;
return 0;
}