#include<bits/stdc++.h>
using namespace std;

int a[4][4],b[4][4];

int step[3265920+5];//step[i] 代表走到状态i所需要的最小步数 
int belong[3265920+5];
//belong[i]==0 代表这个状态还没有被搜到
//belong[i]==1 代表这个状态是从起点被搜到的
//belong[i]==2 代表这个状态是从终点被搜到的 

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[9];//vis[i]i这个数有没有出现过
int fac[10];//fac[i] 代表i!  

signed main(){
	fac[0]=1;
	for (int i=1;i<=9;i++)
		fac[i]=fac[i-1]*i;//首先处理阶乘 
	
	int s;
	cin>>s;
	int ss=s;
	
	for(int i=3;i>=1;i--)
		for(int j=3;j>=1;j--){
			a[i][j]=ss%10;
			ss/=10;
		}
		
	ss=0;
	for (int i=3;i>=1;i--)
		for (int j=3;j>=1;j--){	
			vis[a[i][j]]=true;//标记已经遍历 
			int cnt=0;//查看前面有几个比它大的数 
			for (int k=0;k<a[i][j];k++)
				if(!vis[k]) cnt++;
			s=s+cnt*fac[(i-1)*3+j];//存储下来 
		}
			
	memset(step,-1,sizeof(step));
	step[ss] = 0;
	belong[ss] = 1;
	step[46718]=0; belong[46718] = 2;
	queue<int> q;
	q.push(ss);
	q.push(46718); 
	while (q.size()){
		int s=q.front();
		int cur_step = step[s];
		int cur_belong = belong[s];
		q.pop();
		int x,y;
		memset(vis,false,sizeof(vis));
		
		for (int i=3;i>=1;i--)
			for (int j=3;j>=1;j--){
				vis[a[i][j]]=true;
				int cnt=0;
				for(int k=0;k<a[i][j];k++)
					if(!vis[k]) cnt++;
				ss=ss+cnt*fac[(i-1)*3+j];
			}
				
		for (int i=0;i<9;i++)
			if (!vis[i]) a[3][3] = i;
			
		for (int i=1;i<=3;i++)
			for (int j=1;j<=3;j++)
				if (a[i][j]==0) x=i,y=j;
				
		for (int d=0;d<4;d++){
			int xx=x+dx[d];
			int yy=y+dy[d];//(x,y) 和 (xx,yy)交换
			
			if (xx>=1 && xx<=3 && yy>=1 && yy<=3){
				swap(a[x][y],a[xx][yy]);
				s=0;
				for (int i=1;i<=3;i++)
					for (int j=1;j<=3;j++)
						if (i!=3 || j!=3) s=s*10+a[i][j];
						
				if (step[s] == -1){
					step[s] = cur_step+1;//从起点来的，步数+1 
					belong[s] = cur_belong;//从终点来的 
					q.push(s);
				}
				
				else if (belong[s] != cur_belong){//相交 
					int ans = cur_step + 1 + step[s];//从起点到这个点的步数话从终点到这个点的步数相加再+1 
					cout << ans << endl;
					exit(0);
				}
				swap(a[x][y],a[xx][yy]);
			} 
		}
	}
	cout << step[46718] << endl;
}

用的双向BFS+利用阶乘方法优化空间，第 $i$ 个数用小于等于 $i$ 的数中未枚举到（未删去）的数量 乘上 $9-i$ 的阶乘。