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

/*----------       定数定義       ----------*/

#define BOARD_SIZE          3       // パズルの行数（列数）
#define PANEL_NUM           9       // マスの総数
#define MAX_PATTERN         362880  // 考えられるパズルの組み合わせ数 (9の階乗)
#define MOVE_DIRECTION_NUM  4       // 移動方向の数
#define MALLOC_ERR         -1       // メモリ確保失敗
#define SEARCH_FAILURE     -2       // 探索失敗


/*----------      構造体宣言      ----------*/

/*
 *  パズル盤面の情報をもつ構造体
 */
typedef struct {
    int field[PANEL_NUM];   // パズルの配置
    int space_position;     // 空白の位置
    int num_moves;          // 手数
} Puzzle;

/*
 *  キューを実装するための構造体
 */
typedef struct {
    Puzzle *data;
    int head;
    int tail;
} Queue;


/*----------   プロトタイプ宣言   ----------*/

bool Init(Queue *queue);
bool isEmpty(Queue *queue);
void Push(Queue *queue, Puzzle puzzle);
Puzzle Pop(Queue *queue);
int CalcHashValue(int *field);
int BreadthFirstSearch(Puzzle *start);
void swap(int*a,int*b);


/*----------      メイン処理      ----------*/

int main() {
    Puzzle start;

    // 初期配置の読み込み
    for(int i = 0; i < PANEL_NUM; i++ ){
        scanf("%d", &start.field[i]);
        if(start.field[i] == 0){
            start.space_position = i;
        }
    }

    int answer = BreadthFirstSearch(&start); // 幅優先探索で最短手数を求める

    if(answer == MALLOC_ERR){
        printf("malloc error\n");
    }
    else if(answer == SEARCH_FAILURE){
        printf("探索失敗r\n");
    }
    else{
        printf("%d\n", answer);
    }
    return EXIT_SUCCESS;
}


/*----------       関数定義       ----------*/

/*
 *  幅優先探索でパズルの最短手数を求める
 *
 *  戻り値：
 *      探索に成功した場合    最短手数
 *      mallocに失敗した場合  MALLOC_ERR
 *      探索に失敗した場合    SEARCH_FAILURE
 */
int BreadthFirstSearch(Puzzle *start) {
    start->num_moves = 0;

    Queue queue;

    if(!Init(&queue)){
        return MALLOC_ERR;
    }
    Push(&queue, *start);

    bool *hash_table = (bool*) malloc(sizeof(bool) * MAX_PATTERN);  // 一度探索した配置を覚えておくためのテーブル
    if(!hash_table){
    	free(queue.data);
        return MALLOC_ERR;
    }

    int goal_field[PANEL_NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 0};   // ゴールの配置
    int goal_hash_value = CalcHashValue(goal_field);         // ゴールのハッシュ値

    hash_table[CalcHashValue(start->field)] = true;

    // 上、左、下、右の空白の移動方向を定義
    const int move_direction_x[MOVE_DIRECTION_NUM] = {-1, 0, 1, 0};
    const int move_direction_y[MOVE_DIRECTION_NUM] = {0, -1, 0, 1};

    while(!isEmpty(&queue)){
        Puzzle now = Pop(&queue); // キューの先頭の盤面を取り出す

        // 現在のハッシュ値とゴールのハッシュ値が一致したら終了
        if(CalcHashValue(now.field) == goal_hash_value){
        	free(queue.data);
        	free(hash_table);
        	return now.num_moves;
        }

        int now_space_pos_x = now.space_position / BOARD_SIZE;
        int now_space_pos_y = now.space_position % BOARD_SIZE;

        // 上下左右の4方向に空白を移動した際の盤面をキューに追加する
        for(int i = 0; i < MOVE_DIRECTION_NUM; i++){
            int moved_space_pos_x = now_space_pos_x + move_direction_x[i];
            int moved_space_pos_y = now_space_pos_y + move_direction_y[i];

            if(moved_space_pos_x < 0 || moved_space_pos_y < 0 || moved_space_pos_x >= BOARD_SIZE || moved_space_pos_y >= BOARD_SIZE){
                continue;  // 移動後の空白の位置がパズルの枠から出ている場合は次へ
            }

            Puzzle next = now; // 空白を移動した際の盤面を作成

            int moved_space_posision = moved_space_pos_x * BOARD_SIZE + moved_space_pos_y;

            // 空白位置の移動
            swap(&next.field[now.space_position], &next.field[moved_space_posision]);

            next.space_position = moved_space_posision;

            int next_puzzle_hash_value = CalcHashValue(next.field);  // 動かした盤面のハッシュ値

            // 盤面が重複しているかを調べる
            if(!hash_table[next_puzzle_hash_value]){
            	// 重複が無ければハッシュテーブルを更新し、盤面をキューに追加する
                hash_table[next_puzzle_hash_value] = true;
                next.num_moves++;
                Push(&queue, next);
            }
        }
    }

    // ゴール盤面にたどり着かずに、キューが空になった場合は探索失敗
    free(queue.data);
    free(hash_table);
    return SEARCH_FAILURE;
}

/*
 *  キューを初期化する
 *
 *  戻り値：
 *      初期化に成功すれば true、失敗すれば false
 */
bool Init(Queue *queue) {
    queue->head = 0;
    queue->tail = 0;
    queue->data = (Puzzle*) malloc(sizeof(Puzzle) * MAX_PATTERN);
    if(!queue->data){
        return false;
    }
    return true;
}

/*
 *  キューが空がどうか調べる
 *
 *  戻り値：
 *      空であれば true、そうれなければ false
 */
bool isEmpty(Queue *queue) {
    return queue->head == queue->tail;
}

/*
 *  キューに要素を追加する
 *
 *  戻り値:
 *      なし
 */
void Push(Queue *queue, Puzzle puzzle) {
    queue->data[queue->tail] = puzzle;
    queue->tail = (queue->tail + 1) % MAX_PATTERN;
}

/*
 *  キューの先頭要素を取り出す
 *
 *  戻り値：
 *      キューの先頭要素のパズル
 */
Puzzle Pop(Queue *queue) {
    Puzzle puzzle = queue->data[queue->head];
    queue->head = (queue->head + 1) % MAX_PATTERN;
    return puzzle;
}

/*
 *  パズル盤面のハッシュ値を計算する
 *
 *  戻り値：
 *      盤面のハッシュ値
 */
int CalcHashValue(int *field) {
    int res = 0;
    int fac[] = {40320, 5040, 720, 120, 24, 6, 2, 1};
    int fac_idx = 0;
    bool used_num[PANEL_NUM] = {};
    for(int i = 0; i < PANEL_NUM; i++){
        int count = 0;
        used_num[field[i]] = true;
        for(int j = 0; j < field[i] ; j++){
            if(used_num[j]){
                continue;
            }
            count++;
        }
        res += count * fac[fac_idx++];
    }
    return res;
}

/*
 *  値を入れ替える
 *
 *  戻り値:
 *      なし
 */
void swap(int*a,int*b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}



Measured memory_bytes: 9656