#include<stdio.h>
#include<stdlib.h>
#define Size 9
#define Edge 3
#define Heap_size 102400
#define Hash_size 102400
#define Goal_val 0x123456780LL
struct heap_table {
  long long data;
  int space;
  int depth;
  int score;
};
struct hash_table {
  long long data;
  struct hash_table *next;
};
int goal_score, heapsize, dir[Size], to[Size][4];
struct heap_table heap[Heap_size];
struct hash_table *hash[Hash_size];

long long swap(int*, int, int);
long long board_val(int*);
void val_board(long long, int*);
int fair_evaluate(int*, int *);
void downheap(int);
void upheap(int);
void hash_insert(long long);
int hash_search(long long);
int Bfs(int*, int*, int);
int main(void)
{
  int i, j, result, space, init[Size], goal[Size];
  for (i = 0; i < Hash_size; i++) hash[i] = NULL;
  for (i = 0; i < Size; i++) {
    int dcount = 0;
    scanf("%d", &init[i]);
    if (!init[i]) space = i;
    goal[i] = (i + 1) % Size;
    if (i > Edge - 1) to[i][dcount++] = i - Edge;
    if (i % Edge) to[i][dcount++] = i - 1;
    if ((i + 1) % Edge) to[i][dcount++] = i + 1;
    if (i < Size - Edge) to[i][dcount++] = i + Edge;
    dir[i] = dcount;
  }
  for (i = 0; i < Size / 2; i++) goal_score += goal[Size - 1 - i] - goal[i];
  printf("%d\n", Bfs(init, goal, space));
}
long long swap(int *board, int space, int next)
{
  int i;
  long long res = 0;
  for (i = 0; i < Size; i++) {
    res <<= 4;
    if (i == space) res |= board[next];
    if (i == next) res |= board[space];
    else res |= board[i];
  }
  return res;
}
long long board_val(int *board)
{
  int i;
  long long val = 0;
  for (i = 0; i < Size; i++) {
    val <<= 4;
    val |= board[i];
  }
  return val;
}
void val_board(long long val, int *board)
{
  int i;
  for (i = 0; i < Size; i++) {
    board[Size - 1 - i] = val & 0xf;
    val >>= 4;
  }
}
int fair_evaluate(int *board, int *goal) {
  int i, j, score = 0;
  for (i = 1; i < Size; i++) {
    int x1, y1, x2, y2;
    for (j = 0; j < Size; j++) {
      if (board[j] == i) {
        x1 = j % Edge;
        y1 = j / Edge;
      }
      if (goal[j] == i) {
        x2 = j % Edge;
        y2 = j / Edge;
      }
    }
    score += abs(x1 - x2) + abs(y1 - y2);
  }
  return score;
}
void downheap(int k) {
  int j;
  struct heap_table v = heap[k];
  while (k < heapsize / 2) {
    j = 2 * k + 1;
    if (j < heapsize - 1 && heap[j].score > heap[j + 1].score) j++;
    if (v.score <= heap[j].score) break;
    heap[k] = heap[j];
    k = j;
  }
  heap[k] = v;
}
void upheap(int j)
{
  int k;
  struct heap_table v = heap[j];
  while (j > 0) {
    k = (j + 1) / 2 - 1;
    if (v.score >= heap[k].score) break;
    heap[j] = heap[k];
    j = k;
  }
  heap[j] = v;
}
void hash_insert(long long val)
{
  struct hash_table *p = (struct hash_table*)malloc(sizeof(struct hash_table));
  p->data = val;
  p->next = hash[val % Hash_size];
  hash[val % Hash_size] = p;
}
int hash_search(long long val)
{
  struct hash_table *n;
  for (n = hash[val % Hash_size]; n != NULL; n = n->next) {
      if (val == n->data) return 1;
  }
  return 0;
}
int Bfs(int *init, int *goal, int spa)
{
  struct heap_table theap;
  int i, board[Size];
  theap.data = board_val(init);
  heap[heapsize].data = theap.data;
  heap[heapsize].space = spa;
  heap[heapsize].depth = 0;
  heap[heapsize++].score = fair_evaluate(init, goal);
  if (theap.data == Goal_val) return 0;
  hash_insert(theap.data);
  while (heapsize > 0) {
    theap.data = heap[0].data;
    val_board(theap.data, board);
    theap.space = heap[0].space;
    theap.depth = heap[0].depth;
    heap[0] = heap[--heapsize];
    downheap(0);
    for (i = 0; i < dir[theap.space]; i++) {
      int next = to[theap.space][i], nboard[Size];
      long long nval = swap(board, theap.space, next);
      if (!hash_search(nval)) {
        if (nval == Goal_val) return theap.depth + 1;
        hash_insert(nval);
        heap[heapsize].data = nval;
        heap[heapsize].space = next;
        heap[heapsize].depth = theap.depth + 1;
        val_board(nval, nboard);
        heap[heapsize++].score = fair_evaluate(nboard, goal) + theap.depth + 1;
        upheap(heapsize - 1);
      }
    }
  }
}


Measured memory_bytes: 3324