#include<stdio.h>
#define N 3
#define MAX 182000
#define MEMO_MAX 380000000
#define MIN 54481005 //パズルを9進数に置換した時の最小
#define TRUE 1
#define FALSE -1

typedef struct{
  int p[N][N]; //パズルの状態を保存
  int dis; //手数
  int u, d, l, r; //すでに遷移した方向を表すフラグ
}puzzle;

int BFS(void);
void copy(int a[N][N], int b[N][N]);
void swap(int *, int *);
int judge(int a[N][N]);
void enqueue(puzzle);
puzzle dequeue(void);
void print(puzzle);

int head = 0;
int tail = 0;
int ans[N][N] = {{1, 2, 3},
		 {4, 5, 6},
		 {7, 8, 0}}; //完成形 
puzzle q[MAX]; //キュー
puzzle s; //u, d, l, r, disはこの時点で初期化されてる
char memo[MEMO_MAX] = {}; //生成した盤面を保存しておく

int main(){
  int i, j;
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      scanf("%d", &s.p[i][j]);
    }
  }

  BFS();
  
  return 0;
}

int BFS(){
  puzzle v;
  int cnt; //完成形と一致している数字の数
  int i0, j0; //空白の位置
  int i, j;

  enqueue(s);

  while(1){
    
    v = dequeue();
    //sの初期化
    s.u = s.d = s.l = s.r = 0;
    s.dis = 0;

    //パズルが完成したら終了
    cnt = 0;
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(v.p[i][j] == ans[i][j]) cnt++;
      }
    }
    if(cnt == N * N){
      printf("%d\n", v.dis);
      return 0;
    }

    //空白の位置を特定
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(v.p[i][j] == 0){
	  i0 = i;
	  j0 = j;
	}
      }
    }

    //上
      if(i0 != 0 && v.u == 0){
	copy(s.p, v.p); //vのパズルの状態をコピーする
	swap(&(s.p[i0][j0]), &(s.p[i0-1][j0]));
	if(judge(s.p) == TRUE){
	  s.d = 1; //下に行かないようにする(無駄に往復しないように)
	  s.dis = v.dis + 1;
	  enqueue(s);
	  s.u = s.d = s.l = s.r = 0;
	  s.dis = 0;
	  //print(s);
	}
      }
      //下
      if(i0 != N-1 && v.d == 0){
	copy(s.p, v.p); //vのパズルの状態をコピーする
	swap(&(s.p[i0][j0]), &(s.p[i0+1][j0]));
	if(judge(s.p) == TRUE){
	  s.u = 1; //上に行かないようにする(無駄に往復しないように)
	  s.dis = v.dis + 1;
	  enqueue(s);
	  s.u = s.d = s.l = s.r = 0;
	  s.dis = 0;
	  //print(s);
	}
      }
      //右
      if(j0 != N-1 && v.l == 0){
	copy(s.p, v.p); //vのパズルの状態をコピーする
	swap(&(s.p[i0][j0]), &(s.p[i0][j0+1]));
	if(judge(s.p) == TRUE){
	  s.r = 1; //左に行かないようにする(無駄に往復しないように)
	  s.dis = v.dis + 1;
	  enqueue(s);
	  s.u = s.d = s.l = s.r = 0;
	  s.dis = 0;
	  //print(s);
	}
      }
      //左
      if(j0 != 0 && v.r == 0){
	copy(s.p, v.p); //vのパズルの状態をコピーする
	swap(&(s.p[i0][j0]), &(s.p[i0][j0-1]));
	if(judge(s.p) == TRUE){
	  s.l = 1; //右に行かないようにする(無駄に往復しないように)
	  s.dis = v.dis + 1;
	  enqueue(s);
	  s.u = s.d = s.l = s.r = 0;
	  s.dis = 0;
	  //print(s);
	}
      }
    
  }

};

void copy(int a[N][N], int b[N][N]){
  int i, j;
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      a[i][j] = b[i][j];
    }
  }
}

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

int judge(int a[N][N]){
  long long key = 0; //ハッシュ
  int x, y = 1;
  int i, j;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      x = a[i][j] + 1;
      key += x * y;
      y *= 9;
    }
  }

  key -= MIN;
  
  //\0はfree, nはnotfree
  if(memo[key] == '\0'){
    memo[key] = 'n';
    return TRUE;
  }
  else return FALSE;
}

void enqueue(puzzle x){
  q[tail] = x;
  if(tail == MAX-1) tail = 0;
  else tail++;
}

puzzle dequeue(void){
  puzzle x;
  x = q[head];
  if(head == MAX-1) head = 0;
  else head++;
  return x;
}

void print(puzzle s){
  int i, j;
  static int x = 1;
  printf("%d\n", x);
  x++;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      printf("%d ", s.p[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}





Measured memory_bytes: 122512