可以用 DFS-ID（迭代加深）做的，但当时没想到，就用 BFS 做了。

代码

#include <bits/stdc++.h>
using namespace std;
const string TGT = "123804765";
map<string,bool> f;
int bfs(string st){
	queue<pair<string,int>> q;
	q.push({st,0});
	f[st] = 1;
	while (!q.empty()){
		string cur = q.front().first;
		int u = q.front().second;
		q.pop();
		if (cur == TGT)	return u;
		int i0 = cur.find('0');
		if (i0 % 3){	// 不在第一列
			swap(cur[i0],cur[i0 - 1]);
			if (!f[cur]){
				f[cur] = 1;
				q.push({cur,u + 1});
			}
			swap(cur[i0],cur[i0 - 1]);
		}
		if (i0 % 3 < 2){	// 不在第三列
			swap(cur[i0],cur[i0 + 1]);
			if (!f[cur]){
				f[cur] = 1;
				q.push({cur,u + 1});
			}
			swap(cur[i0],cur[i0 + 1]);
		}
		if (i0 / 3){	// 不在第一行
			swap(cur[i0],cur[i0 - 3]);
			if (!f[cur]){
				f[cur] = 1;
				q.push({cur,u + 1});
			}
			swap(cur[i0],cur[i0 - 3]);
		}
		if (i0 / 3 < 2){	// 不在第三行
			swap(cur[i0],cur[i0 + 3]);
			if (!f[cur]){
				f[cur] = 1;
				q.push({cur,u + 1});
			}
			swap(cur[i0],cur[i0 + 3]);
		}
	}
}
int main(int argc, char **argv){
	string s;
	cin >> s;
	cout << bfs(s);
	return 0;
}

简洁代码，为了让代码更加简洁，我将原本加了的注释删掉了

#include<bits/stdc++.h>
using namespace std;
int n;
int f[10]={-3,-1,1,3};
string sta;
struct S{int x,ans;string s;};
queue<S> q;
map<string,int> m;
void bfs(){
    while(!q.empty()){
        int x=q.front().x,ans=q.front().ans;
        string s=q.front().s;
        q.pop();
        if(s=="123804765"){cout<<ans;return;}
        if((ans>m[s])) continue;
        m[s]=ans;
        for(int i=0;i<4;i++){
            int nx=x+f[i];
            if(((x==3 || x==6) && i==1) || ((x==5 || x==8 || x==2) && i==2)){continue;}
            if(nx<0 || nx>=n){continue;}
            swap(s[x],s[nx]);
            if(ans+1>m[s] && m[s]!=0){swap(s[x],s[nx]);continue;}
            q.push({nx,ans+1,s});
            m[s]=ans+1;
            swap(s[x],s[nx]);
        }
    }
}
int main(){
    cin>>sta;
    n=sta.size();
    int st=0;
    for(int i=0;i<n;i++) if(sta[i]=='0') st=i;
    q.push({st,0,sta});
    bfs();
    return 0;
}
//123056487

剑丹

#include<bits/stdc++.h>
using namespace std;
int deep;
int xl[4]={-1,1,0,0};
int yl[4]={0,0,-1,1};
bool check(string p)
{
	return p=="@123804765";
}
pair<int,int> txy(int x)
{
	return (pair<int,int>){(x-1)/3+1,(x-1)%3+1};
}
int tx(pair<int,int>x)
{
	return (x.first-1)*3+x.second;
}
int find_0(string p)
{
	for(int i=1;i<p.size();i++)
		if(p[i]=='0')return i;
	return 0;
}
map<string,bool>vis;
queue<pair<string,int> >q;
void bfs(string s)
{
	q.push({s,0});
	while(!q.empty())
	{
		string p=q.front().first;
		int c=q.front().second;
		q.pop();
		if(check(p))
		{
			cout<<c;
			return;
		}
		pair<int,int>xy=txy(find_0(p));
		for(int i=0;i<4;i++)
		{
			int xs=xy.first+xl[i],ys=xy.second+yl[i];
			string np=p;
			swap(np[tx(xy)],np[tx((pair<int,int>){xs,ys})]);
			if(xs<1 || xs>3 || ys<1 || ys>3 || vis.count(np))continue;
			vis[np]=1;
			q.push({np,c+1});
		}
	}
}
int main()
{
	string a;
	cin>>a;
	a="@"+a;
	bfs(a);
	return 0;
}

懒得写双向了

#include<bits/stdc++.h>
using namespace std;
typedef string str;
map<str,int>m1;map<str,int>m2;
queue<str>q1;queue<str>q2;
str a;
int find(str s){
	for(int i=0;i<9;i++){
		if(s[i]=='0')return i;
	}
}
str change(str s,int x){
	str t=s;
	int r=find(t);
	if(x==1){
		if(r<=2)return "bana";
		else{
			swap(t[r],t[r-3]);
			return t;
		}
	}
	else if(x==2){
		if(r>=6)return "bana";
		else{
			swap(t[r],t[r+3]);
			return t;
		}
	}
	else if(x==3){
		if(r%3==0)return "bana";
		else{
			swap(t[r],t[r-1]);
			return t;
		}
	}
	else{
		if(r%3==2)return "bana";
		else{
			swap(t[r],t[r+1]);
			return t;
		}
	}
}
void bfs(){
	q1.push("123804765");
	q2.push(a);
	m1["123804765"]=0;
	m2[a]=0;
	while(!q1.empty()){
		str e=q1.front();q1.pop();
		if(e==a){
			cout<<m1[e]<<'\n';
			exit(0);
		}
		for(int i=1;i<=4;i++){
			str b=change(e,i);
			if(b=="bana")continue;
			if(m1.count(b))continue;
			q1.push(b);
			m1[b]=m1[e]+1;
		}
	}
}
int main(){
	getline(cin,a);
	if(a=="123804765"){
		cout<<0<<'\n';
		return 0;
	}
	bfs();
	return 0;
}