#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;
}
抄了一下张正标的代码