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 }