1 #include<iostream>
2 #include<bits/stdc++.h>
3 using namespace std;
4 #include<vector>
5 using std::vector;
6 bool t[1000000000];
7 int a[4][4];
8 int ans=100000000;
9 int tx[5]={0,0,1,-1,0};
10 int ty[5]={0,-1,0,0,1};
11 int pc[363000];
12 int zt=0;
13 int erfen(int a)
14 {
15 int ans=-1;
16 int l=1,r=zt,mid=(l+r)/2;
17 while(l<=r)
18 {
19 if(pc[mid]>a)
20 {
21 r=mid-1;
22 mid=(l+r)/2;
23 }
24 if(pc[mid]<a)
25 {
26 l=mid+1;
27 mid=(l+r)/2;
28 }
29 if(pc[mid]==a)
30 {
31 ans=mid;
32 return ans;
33 }
34 }
35 return ans;
36 }
37 void bfs(int x,int y,int a[4][4],int sum)
38 {
39
40 if(erfen(a[1][1]*100000000+a[1][2]*10000000+a[1][3]*1000000
41 +a[2][1]*100000+a[2][2]*10000+a[2][3]*1000+a[3][1]*100+a[3][2]*10
42 +a[3][3])!=-1) return ;//如果重复了，直接退出（删除节点）
43 if(a[1][1]*100000000+a[1][2]*10000000+a[1][3]*1000000
44 +a[2][1]*100000+a[2][2]*10000+a[2][3]*1000+a[3][1]*100+a[3][2]*10
45 +a[3][3]==123804765)
46 {
47 if(sum<ans) ans=sum;
48 cout<<"youyigejie"<<endl;
49 return ;
50 } //判断是否目标状态
51 sum++;
52 pc[++zt]=a[1][1]*100000000+a[1][2]*10000000+a[1][3]*1000000
53 +a[2][1]*100000+a[2][2]*10000+a[2][3]*1000+a[3][1]*100+a[3][2]*10
54 +a[3][3];
55 sort(pc,pc+1+zt);
56 for(int i=1;i<=4;i++)
57 if(tx[i]+x>=1&&tx[i]+x<=3&&ty[i]+y>=1&&ty[i]+y<=3)
58 {
59 int t[4][4];
60 for(int i=0;i<=3;i++)
61 for(int j=0;j<=3;j++)
62 t[i][j]=a[i][j];
63 t[x][y]=t[tx[i]+x][ty[i]+y],t[tx[i]+x][ty[i]+y]=0;
64 if(erfen(t[1][1]*100000000+t[1][2]*10000000+t[1][3]*1000000
65 +t[2][1]*100000+t[2][2]*10000+t[2][3]*1000+t[3][1]*100+t[3][2]*10
66 +t[3][3])==-1)bfs(x+tx[i],y+ty[i],t,sum);
67
68 }
69 }
70 int main()
71 {
72
73 int x,y;
74 for(int i=1;i<=3;i++)
75 for(int j=1;j<=3;j++)
76 {
77 cin>>a[i][j];
78 if(a[i][j]==0) x=i,y=j;
79 }
80 bfs(x,y,a,0);
81 cout<<ans<<endl;
82 return 0;
83 }
