#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;
}
浅浅借鉴一下张老师的代码