1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 using namespace std;
5 const int MAXN=5;
6 int xx[5]={-1,+1,0,0};
7 int yy[5]={0,0,-1,+1};
8 struct node
9 {
10 int mp[MAXN][MAXN];
11 }a[100001];
12 int hashfind[3733801];
13 int step[200];
14 int h=0,t=1;
15 int bc[MAXN][MAXN]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};
16 int hash()
17 {
18 int s=0;
19 int k=1;
20 for(int i=1;i<=3;i++)
21 {
22 for(int j=1;j<=3;j++)
23 {
24 s=s+a[t].mp[i][j]*k;
25 k=k*7;
26 }
27 }
28 s=s%3733801;
29 if(hashfind[s]==0)
30 {
31 hashfind[s]=1;
32 return 1;
33 }
34 else
35 {
36 return 0;
37 }
38 }
39 int check()
40 {
41 for(int i=1;i<=3;i++)
42 {
43 for(int j=1;j<=3;j++)
44 {
45 if(a[t].mp[i][j]!=bc[i][j])
46 return 0;
47 }
48 }
49 return 1;
50 }
51 void move(int x,int y)
52 {
53
54 for(int i=0;i<4;i++)
55 {
56 int wx=x+xx[i];
57 int wy=y+yy[i];
58 if(wx>=1&&wx<=3&&wy>=1&&wy<=3)
59 {
60 for(int j=1;j<=3;j++)
61 {
62 for(int k=1;k<=3;k++)
63 {
64 a[t].mp[j][k]=a[h].mp[j][k];
65 }
66 }
67 swap(a[t].mp[wx][wy],a[t].mp[x][y]);
68 step[t]=step[h]+1;
69 if(check()==1)
70 {
71 printf("%d",step[t]);
72 exit(0);// end
73 }
74 if(hash()==1)
75 t++;
76 }
77 }
78 }
79 void bfs()
80 {
81 while(h<t)
82 {
83 for(int i=1;i<=3;i++)
84 {
85 for(int j=1;j<=3;j++)
86 {
87 if(a[h].mp[i][j]==0)
88 {
89 move(i,j);
90 }
91 }
92 }
93 h++;
94 }
95 }
96 int main()
97 {
98 char dr[10];
99 int bgx=0;
100 int bgy=0;
101 gets(dr);
102 int now=0;
103 for(int i=1;i<=3;i++)
104 {
105 for(int j=1;j<=3;j++)
106 {
107 a[0].mp[i][j]=dr[now]-48;
108 if(a[0].mp[i][j]==0)
109 {
110 bgx=i;
111 bgy=j;
112 }
113 now++;
114 }
115 }
116 bfs();
117 return 0;
118 }