#include<stdio.h>
#include<cstdlib>
#include<math.h>
#include<iostream>
#include<queue>

// 参考　https://qiita.com/exrd/items/8bc0be17a15ff77d3754
//      http://www.nct9.ne.jp/m_hiroi/puzzle/eight.html

#define N 9 // マス目の数
#define INF 1000
#define FORWARD 2
#define BACKWARD -2

int sqrtN;

typedef struct {
    int b[N];
    int space;
    int path; // かかった手数
    int prenum; // 前のボードの状態
    int from; // 双方向探索のための値
    int hur; // ヒューリスティック値
}Puzzle;

typedef struct s{
    int num;
    struct s *left;
    struct s *right;
}BoardState;


void t(){
    printf("\ntest\n");
}

void swap(int *x, int *y){
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

// 盤面をプリント
void printBoard(Puzzle p){
    for(int i = 0; i < N; i++){
        printf("%d", p.b[i]);
        if ((i+1) % sqrtN == 0) {
            printf("\n");
        }else{
            printf(" ");
        }
    }
    printf("\n");
}

int kaijou(int x){
    int kaijou = x;
    for(int i = x-1; i > 0; i--){
        kaijou *= i;
    }
    return kaijou;
}

// 盤面の状態を数字に変換　参考:http://www.nct9.ne.jp/m_hiroi/puzzle/eight.html
int culcBoardNum(Puzzle p){
    for (int i = 0; i < N-1; i++) {
        for (int j = i+1; j < N; j++) {
            //printf("%d %d\n", p.b[i], p.b[j]);
            if(p.b[i] < p.b[j]){
                p.b[j]--;
            }
        }
    }
    //printBoard(p);
    int num = 0;
    for(int i = 0; i < N-1; i++){
        num += p.b[i] * kaijou(N-1-i);
    }
    
    return num;
}

// 空いたスペースの上下左右があるか確かめる関数たち
int left(Puzzle p){
    if(p.space % sqrtN == 0){
        return 0;
    }else{
        return p.b[p.space-1];
    }
}

int right(Puzzle p){
    if((p.space+1) % sqrtN == 0){
        return 0;
    }else{
        return p.b[p.space+1];
    }
}

int up(Puzzle p){
    if(p.space < sqrtN){
        return 0;
    }else{
        return p.b[p.space-sqrtN];
    }
}

int down(Puzzle p){
    if(p.space + 1 + sqrtN > N){
        return 0;
    }else{
        return p.b[p.space+sqrtN];
    }
}

// 完成した盤面ならtrueを返す
bool isDone(Puzzle p){
    for(int i = 1; i < N; i++){
        if(p.b[i-1] != i){
            return false;
        }
    }
    return true;
}

//   0 1 2
//   -----   N = 9のとき
//0 |1 2 3
//1 |4 5 6
//2 |7 8 0
int x(int i){
    if(i == 0){
        return sqrtN-1;
    }else{
        return (i-1) % sqrtN;
    }
}
int y(int i){
    if(i == 0){
        return sqrtN-1;
    }else{
        return ( (i-1) - (i-1)%sqrtN ) / sqrtN;
    }
}

// ヒューリスティック値返す xの差分+yの差分
int h(Puzzle p){
    int sum = 0;
    for(int i = 1; i < N; i++){
        sum += abs(x(i) - x(p.b[i-1])) + abs(y(i) - y(p.b[i-1]));
    }
    sum += abs(x(0) - x(p.b[N-1])) + abs(y(0) - y(p.b[N-1]));
    return -1;
}

// すでにでてきた盤面ならtrueを返す
int *allboard; // でできた盤面を数字にして格納 mainでmalloc [1]からスタート
int *fromwhere; // どっちからきたか記録　allbaordと対応
int *paths; // allboardと対応
int curboardNum = 0; // 今のallboardの要素数
BoardState bs_root;
int isAlready(Puzzle p){
    //printf("isAlready\n");
    int nump = culcBoardNum(p);
    
    // 線形探索
    /*
    for(int i = 0; i < curboardNum; i++){
        //printf("%d: %d to %d\n", i, allboard[i], nump);
        if (nump == allboard[i]) {
            return true;
        }
    }
    allboard[curboardNum] = nump;
    curboardNum++;
    return false;*/
    
    // もう作った盤面で来た方向が違ければ一致した方のpathを返す
    for(int i = 0; i < curboardNum; i++){
        if (nump == allboard[i] && p.from != fromwhere[i]) {
            //printf("%d番目\n", i);
            return paths[i] + p.path;
        }
    }
    allboard[curboardNum] = nump;
    fromwhere[curboardNum] = p.from;
    paths[curboardNum] = p.path;
    /*for(int i = 0; i < curboardNum+1; i++){
        printf("%d ", paths[i]);
    }
    printf("\n");*/
    curboardNum++;
    return 0;
    
    // 二分探索木
    /*while (1) {
     if(allboard[i] == -1){
     allboard[i] = nump;
     return false;
     }else if(allboard[i] == nump){
     return true;
     }else if(allboard[i] < nump){
     i = 2*i;
     }else{
     i = 2*i + 1;
     }
     }*/
    // 連結リストの二分木
    /*
    BoardState bs, newly;
    bs = bs_root;
    while (1) {
        if (bs.num == nump) {
            return true;
        }else if(bs.num > nump){
            if(bs.left == NULL){
                bs.left = &newly;
                bs.left->num = nump;
                return false;
            }else{
                bs = *(bs.left);
            }
        }else if(bs.num < nump){
            if(bs.right == NULL){
                bs.right = &newly;
                bs.right->num = nump;
                return false;
            }else{
                bs = *(bs.right);
            }
        }
    }*/

}
int whilecount = 0;
// ---- // ---- //
// 最短手数を返す
int bfs(Puzzle p){
    if(isDone(p)){
        return 0;
    }
    std::queue<Puzzle> Q;
    
    Puzzle v, goal, l, r, u, d;
    int minpath;
    
    p.path = 0;
    //p.hur = h(p);
    p.prenum = -1;
    p.from = FORWARD;
    // goal初期化
    for (int i = 1; i < N; i++) {
        goal.b[i-1] = i;
    }
    goal.b[N-1] = 0;
    goal.path = 0;
    goal.prenum = -1;
    goal.from = BACKWARD;
    goal.space = N-1;
    
    Q.push(p);
    Q.push(goal);
    allboard[0] = culcBoardNum(p);
    allboard[1] = culcBoardNum(goal);
    fromwhere[0] = FORWARD;
    fromwhere[1] = BACKWARD;
    paths[0] = 0;
    paths[1] = 0;
    curboardNum += 2;
    bs_root.num = culcBoardNum(p);
    while (1) {
        v = Q.front();
        Q.pop();
        int hurv = h(v);
        int numv = culcBoardNum(v);
        /*printf("dequeue %s\n", v.from == FORWARD ? "FORWARD" : "BACKWARD");
        printBoard(v);*/
        // キューの先頭に入っていた盤面から一手動かしてそれをまたキューに入れる　完成したらそこでreturn
        if (left(v)) { // spaceとそのleftを入れ替えられるなら
            l = v; // コピー
            swap(&l.b[l.space], &l.b[l.space-1]); // 入れ替え
            l.space--; // space位置変更
            l.path = v.path + 1;
            /*if (isDone(l)) { // 完成してたら終わり
                return v.path + 1;
            }else if(v.prenum != culcBoardNum(l) && h(l) <= hurv){
                l.prenum = numv;
                l.path = v.path + 1;
                Q.push(l);
            }*/
            /*if(isAlready(l)){
                return l.path + paths[curboardNum] +1;
            }else if(v.prenum != culcBoardNum(l)){
                l.prenum = numv;
                l.from = v.from;
                Q.push(l);
                printf("left path:%d\n", l.path);
                printBoard(l);
            }*/
            if(v.prenum != culcBoardNum(l)){
                minpath = isAlready(l); // ０が帰って来たらまだ終了でない
                if (minpath) {
                    return minpath;
                }else{
                    l.prenum = numv;
                    l.from = v.from;
                    Q.push(l);
                    /*printf("left path:%d\n", l.path);
                    printBoard(l);*/
                }
            }
        }
        // 以下同様
        if (right(v)) {
            r = v;
            swap(&r.b[r.space], &r.b[r.space+1]);
            r.space++;
            r.path = v.path + 1;
            /*if (isDone(r)) {
                return v.path + 1;
            }else if(v.prenum != culcBoardNum(r) && h(r) <= hurv){
                r.prenum = numv;
                r.path = v.path + 1;
                Q.push(r);
            }*/
            /*if(isAlready(r)){
                return r.path + paths[curboardNum] +1;
            }else if(v.prenum != culcBoardNum(r)){
                r.prenum = numv;
                r.from = v.from;
                Q.push(r);
                printf("right path:%d\n", r.path);
                printBoard(r);
            }*/
            if(v.prenum != culcBoardNum(r)){
                minpath = isAlready(r);
                if (minpath) {
                    return minpath;
                }else{
                    r.prenum = numv;
                    r.from = v.from;
                    Q.push(r);
                    /*printf("right path:%d\n", r.path);
                    printBoard(r);*/
                }
            }
        }
        if (up(v)) {
            u = v;
            swap(&u.b[u.space], &u.b[u.space-sqrtN]);
            u.space -= sqrtN;
            u.path = v.path + 1;
            /*if (isDone(u)) {
                return v.path + 1;
            }else if(v.prenum != culcBoardNum(u) && h(u) <= hurv){
                u.prenum = numv;
                u.path = v.path + 1;
                Q.push(u);
            }*/
            /*if(isAlready(u)){
                return u.path + paths[curboardNum] +1;
            }else if(v.prenum != culcBoardNum(u)){
                u.prenum = numv;
                u.from = v.from;
                Q.push(u);
                printf("up path:%d\n", u.path);
                printBoard(u);
            }*/
            if (v.prenum != culcBoardNum(u)) {
                minpath = isAlready(u);
                if (minpath) {
                    return minpath;
                }else{
                    u.prenum = numv;
                    u.from = v.from;
                    Q.push(u);
                    /*printf("up path:%d\n", u.path);
                    printBoard(u);*/
                }
            }
        }
        if (down(v)) {
            d = v;
            swap(&d.b[d.space], &d.b[d.space+sqrtN]);
            d.space += sqrtN;
            d.path = v.path + 1;
            /*if (isDone(d)) {
                return v.path + 1;
            }else if(v.prenum != culcBoardNum(d) && h(d) <= hurv){
                d.prenum = numv;
                d.path = v.path + 1;
                Q.push(d);
            }*/
            /*if(isAlready(d)){
                return d.path + paths[curboardNum] +1;
            }else if(v.prenum != culcBoardNum(d)){
                d.prenum = numv;
                d.from = v.from;
                Q.push(d);
                printf("down path:%d\n", d.path);
                printBoard(d);
            }*/
            if (v.prenum != culcBoardNum(d)) {
                minpath = isAlready(d);
                if (minpath) {
                    return minpath;
                }else{
                    d.prenum = numv;
                    d.from = v.from;
                    Q.push(d);
                    /*printf("down path:%d\n", d.path);
                    printBoard(d);*/
                }
            }
        }
        
        whilecount++;
    }
    return -1;
}

int main(){
    int board;
    Puzzle p;
    
    int kaijouN = kaijou(N);
    allboard = (int *)malloc(sizeof(int) * 30000);
    fromwhere = (int *)malloc(sizeof(int) * 30000);
    paths = (int *)malloc(sizeof(int) * 30000);
    
    bs_root.right = NULL;
    bs_root.left = NULL;
    
    sqrtN = sqrt(N);
    
    for (int i = 0; i < N; i++) {
        scanf("%d", &board);
        if(board == 0){
            p.space = i;
        }
        p.b[i] = board;
        p.path = -1;
    }
    
    //printBoard(p);
    printf("%d\n", bfs(p));
    
    free(allboard);
    free(fromwhere);
    free(paths);
    
    return 0;
}



Measured memory_bytes: 3956