#include<stdio.h>
#include<stdlib.h>

 int puzle[3][3];
 int tmp[3][3];
 int d1[4]={0,1,0,-1};
 int d2[4]={1,0,-1,0};
 
 void empty(int *x,int *y){
                           int i,j;
                           for(i=0;i<3;i++){
                                            for(j=0;j<3;j++){
                                                             if(!puzle[i][j]){
                                                                              *x=j;
                                                                              *y=i;
                                                                              return;
                                                                              }
                                                              }
                                             }
                            }

 void swap(int *a,int *b){
                          int tmp=*a;
                          *a=*b;
                          *b=tmp;
                          }

 int cal(){
           int a,i,sum=0;
           for(i=0;i<9;i++){
                            a=puzle[i/3][i%3];
                            if(a){
                                  a--;
                                  sum+=abs(i/3-a/3)+abs(i%3-a%3);
                                  }
                            }
           return sum;
           }

 int dfs(int x,int y,int p,int dep,const int lim){
       int i,h,n1,n2,res;
       h=cal();
       if(h==0){
                return dep;
                }
       if(dep+h>lim){
                     return -1;
                     }
       for(i=0;i<4;++i){
                        n1=x+d1[i];
                        n2=y+d2[i];
 
                        if(~p&&i==(p+2)%4)continue;
                        if(!(0<=n1&&n1<3&&0<=n2&&n2<3))continue;
                        swap(&puzle[y][x],&puzle[n2][n1]);
                        res=dfs(n1,n2,i,dep+1,lim);

                        if(~res)return res;
 
                        swap(&puzle[y][x],&puzle[n2][n1]);
                        }
       return -1; 
       }

 int main(){
            int ans,x,y,l,i,j;

            for(i=0;i<3;i++){
                             for(j=0;j<3;j++){
                                              scanf("%d",&puzle[i][j]);
                                              }
                             }
            empty(&x,&y);
            for(l=0;l<100;l++){
                               for(i=0;i<3;i++){
                                                for(j=0;j<3;j++){
                                                                 tmp[i][j]=puzle[i][j];
                                                                 }
                                                }
                                ans=dfs(x,y,-1,0,l);
                                if(ans!=-1){
                                            printf("%d\n",ans);
                                            break;
                                            }
                                for(i=0;i<3;i++){
                                                 for(j=0;j<3;j++){
                                                                  puzle[i][j]=tmp[i][j];
                                                                  }
                                                 }
                                ans=-1;
                                if(l==99)printf("%d\n",ans);
                                }
            return 0;
            }









Measured memory_bytes: 2116