#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int sx , ex = 123804765 , mat[3][3] , tx , ty;
int dx[] = {-1 , 1, 0 , 0};
int dy[] = {0 , 0 , 1, -1};
map<int , int> state;//存储当前状态
map<int , int> ans;//当前值 
queue<int> q1 , q2;
//把x转成二维数组 
void toMap(int x)
{
	//283104765
	int div = 100000000;
	for(int i = 0; i < 3; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			mat[i][j] = x / div % 10;
			div /= 10;
			if(!mat[i][j])
				tx = i , ty = j;
		}
	}
}
//把二维数组转成int 
int toInt()
{
	int ans = 0;
	for(int i = 0 ; i < 3; i++)
	{
		for(int j = 0; j < 3; j++)
			ans = ans * 10 + mat[i][j];
	}
	return ans;
}

void bfs( int x)
{
	q1.push(x);//从头到尾 
	q2.push(ex);//从尾到头 
	state[x] = 1;//标记方向 
	state[ex] = 2;//标记方向
	ans[x] = 1;//记录当前状态一共走了多少步 
	ans[ex] = 1; 
	while(!q1.empty() || !q2.empty())
	{
		int top;
		bool flag = 0;
		
		//判断当前操作是从前往后还是从后往前 
		if(q1.size() > q2.size())
		{
			top = q2.front();
			q2.pop();
		}
		else
		{
			top = q1.front();
			q1.pop();
			flag = 1;//记录当前是哪个方向 
		}
		
		
		//top转换成二维数组
		toMap(top);
		
		//tx , ty枚举邻接节点
		for(int i = 0 ; i < 4; i++)
		{
			int xx = tx + dx[i];
			int yy = ty + dy[i];
			//判断
			if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
			{
				swap(mat[xx][yy] , mat[tx][ty]);
				int newX = toInt();//转成int类型数据
				 
				if(!ans.count(newX))//说明newX没有出现过 
				{
					if(flag)
					{
						q1.push(newX);
						state[newX] = 1;
						ans[newX] = ans[top] + 1;
					}
					else
					{
						q2.push(newX);
						state[newX] = 2;
						ans[newX] = ans[top] + 1;
					}
				}
				else if(state[top] + state[newX] == 3)//
				{
					cout << ans[newX] + ans[top] - 1 ;
					exit(0); 
				} 
				swap(mat[xx][yy] , mat[tx][ty]);
			}	
		} 
	}
}

int main()
{
	cin >> sx;//起点 
	if(sx == ex)
	{
		cout << 0;
		return 0;
	}
	bfs( sx );
	return 0;
}
浅浅借鉴一下张老师的代码

#include<iostream>
#include<cstdio>
#include<string>
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int sx,ex=123804765,a[3][3],tx,ty;
queue<int> q1,q2;//q1表示正序队列	q2表示逆序队列 
map<int,int> state,ans;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void toMap(int x){
	for(int i=2;i>=0;i--){
		for(int j=2;j>=0;j--){
			a[i][j]=x%10;
			x/=10;
			if(!a[i][j]) tx=i,ty=j;
		}
	}
}
int toInt(){
	int ans=0;
	for(int i=0;i<=2;i++){
		for(int j=0;j<=2;j++){
			ans=ans*10+a[i][j];
		}
	}
	return ans;
}
void bfs(){
	q1.push(sx);
	q2.push(ex);
	state[sx]=1;
	state[ex]=2;
	ans[sx]=1;
	ans[ex]=1;
	while(!q1.empty()||!q2.empty()){
		int top;
		bool flag=0;
		if(q1.size()<q2.size()){
			top=q1.front();
			q1.pop();
			flag=1;
		}else{
			top=q2.front();
			q2.pop();
		}
		toMap(top);
		for(int i=0;i<=3;i++){
			int xx=tx+dx[i];
			int yy=ty+dy[i];
			if(xx>=0&&xx<=2&&yy>=0&&yy<=2){
				swap(a[xx][yy],a[tx][ty]);
				int newx=toInt();
				if(!state.count(newx)){
					if(flag){
						q1.push(newx);
						state[newx]=1;
						ans[newx]=ans[top]+1;
					}
					else{
						q2.push(newx);
						state[newx]=2;
						ans[newx]=ans[top]+1;
					}
				}
				else if(state[newx]+state[top]==3){
					cout<<ans[newx]+ans[top]-1;
					exit(0);
				}
				swap(a[xx][yy],a[tx][ty]);
			}
		}
	}
}
int main(){
	cin>>sx;
	if(sx==ex){
		cout<<0;
		return 0;
	}
	bfs();
	return 0;
}
抄了一下张正标的代码