type
vj=record
map:array[1..3,1..3]of longint;
k,t,p:longint;
end;
var
d:array[1..50000]of vj;
s:string;
i,j,k,t,p,p1,g,n,m:longint;
a:array[1..3,1..3]of longint;
b:array[1..9]of longint;
vis:array[1..500000]of boolean;
function fac(n:longint):longint;
var i,k:longint;
begin
k:=1;
for i:=1 to n do
k:=k*i;
fac:=k;
end;
function check:longint;
var i,j,temp,num:longint;
begin
num:=0;
for i:=1 to 8 do
begin
temp:=0;
for j:=i+1 to 9 do
if b[j]<b[i] then inc(temp);
num:=num+fac(9-i)*temp;
end;
check:=num+1;
end;
procedure bfs(x,y:longint);
var head,tail,i,x1,y1,f,j:longint;
begin
head:=0;tail:=1;d[1].k:=x;d[1].t:=y;d[1].p:=0;d[1].map:=a;
repeat
inc(head);
x:=d[head].k;
y:=d[head].t;
a:=d[head].map;
for i:=1 to 4 do
begin
x1:=x+step[i,1];
y1:=y+step[i,2];
if (x1<1)or(y1<1)or(x1>3)or(y1>3) then continue;
inc(tail);
d[tail].map:=a;
f:=d[tail].map[x1,y1];
d[tail].map[x1,y1]:=d[tail].map[x,y];
d[tail].map[x,y]:=f;
b[1]:=d[tail].map[1,1];
b[2]:=d[tail].map[1,2];
b[3]:=d[tail].map[1,3];
b[4]:=d[tail].map[2,1];
b[5]:=d[tail].map[2,2];
b[6]:=d[tail].map[2,3];
b[7]:=d[tail].map[3,1];
b[8]:=d[tail].map[3,2];
b[9]:=d[tail].map[3,3];
for j:=1 to 9 do
if b[j]=0 then b[j]:=9;
d[tail].k:=x1;
d[tail].t:=y1;
d[tail].p:=d[head].p+1;
if vis[check] then dec(tail)
else
begin
vis[check]:=true;
with d[tail] do
if (map[1,1]=1)and(map[1,2]=2)and(map[1,3]=3)and(map[2,1]=8)and(map[2,2]=0)and(map[2,3]=4)and(map[3,1]=7)and(map[3,2]=6)and(map[3,3]=5)then
begin
writeln(d[tail].p);
close(input);close(output);
halt;
end
end;
end;
until head>=tail;
end;
begin
readln(s);
for i:=1 to 9 do
begin
p:=i;
if i mod 3<>0 then begin g:=i div 3+1;p1:=i mod 3;end
else begin g:=i div 3;p1:=i mod 3+3;end;
a[g,p1]:=ord(s[p])-48;
b[p]:=ord(s[p])-48;if b[p]=0 then b[p]:=9;
if a[g,p1]=0 then begin n:=g;m:=p1;end;
end;
d[1].map:=a;
bfs(n,m);
end.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct bt
{
int a[362881],step[362881];
int head,tail;
int b[362881];
void clear();
void hash(short x);
void antihash();
void bfs(short x);
void work(short x,short y,short z);
}que[2];
short t[9]={1,2,3,8,0,4,7,6,5};bool v[9];
int jie[9]={40320,5040,720,120,24,6,2,1,1};
short tt,ttt;char ch;
void bt::clear()
{
memset(b,-1,sizeof(b));head=1;step[1]=-1;
}
void bt::hash(short x)
{
int sum=0;
memset(v,false,sizeof(v));
for (short i=0;i<9;i++)
{
for (short j=0;j<t[i];j++)
if (!v[j]) sum+=jie[i];
v[t[i]]=true;
}
sum++;
if (b[sum]>-1) return;
tail++;a[tail]=sum;step[tail]=step[head]+1;b[sum]=step[tail];
if (que[1-x].b[sum]>-1) {printf("%d\n",que[1-x].b[sum]+b[sum]);exit(0);}
}
void bt::antihash()
{
int sum=0;
memset(v,false,sizeof(v));
for (short i=0;i<9;i++)
for (short j=0;j<9;j++)
if (!v[j])
if (sum+jie[i]<a[head]) sum+=jie[i]; else
{
t[i]=j;v[j]=true;
if (j==0) tt=i;
break;
}
}
void bt::work(short x,short y,short z)
{
ttt=t[x];t[x]=t[y];t[y]=ttt;
que[z].hash(z);
ttt=t[x];t[x]=t[y];t[y]=ttt;
}
void bt::bfs(short x)
{
int tstep=step[head];
while (step[head]==tstep)
{
antihash();
if (tt-3>=0) work(tt,tt-3,x);
if (tt+3<9) work(tt,tt+3,x);
if (tt%3>0) work(tt,tt-1,x);
if (tt%3<2) work(tt,tt+1,x);
head++;
}
}
int main()
{
que[0].clear();que[1].clear();
que[0].hash(0);
for (short i=0;i<9;i++) {scanf("%c",&ch);t[i]=ch-'0';}
que[1].hash(1);
while (true)
if (que[0].tail-que[0].head<=que[1].tail-que[1].head) que[0].bfs(0); else que[1].bfs(1);
}