////////////////////////////////////////
//
////////////////////////////////////////

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream

//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert


using namespace std;

#define TEST //*******************************************************************************************************************************************
//?????????????????¨??§?????\????????????????????????????????°?????????????¨???????????????????dout???????????????????????§???????????¬??????????????????????????????????????????
//??????????????????????????????????????????????????????????§?CPU???????£??????????????????§???TLE?????????????????????????????????????????§????????¨???                           ????????????????????????cerr????????£????????????????????????????????????
#ifdef TEST
#define dout cout
#define din cin
#else
stringstream dummy; //???????????°??????dout?????????????????????????????????
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummy?????????????????????????????????????????¨?????¢?????¢???????????????
//???????????¨??????????????????goodbit?????????????????????????????¨???????????´????????????????????????????????¨?????°?????????????????§???????????????????????????????????? http://d.hatena.ne.jp/linden/20060427/p1
#endif

//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile //??¨????????????TLE????????§?????????dout?????¨??¨??????????????¢????????????????????????????????????????????§????¨????????????´??????????????£??????????????????????¨?????????????????????????????????????????????§?????????????????????
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif

//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILE???.
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif


#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl

#define p(i) (i)/2
#define l(i) (i)*2
#define r(i) (i)*2+1

struct d {int n, m, r, l;}; //for Binary Search Tree

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

const int INF = 2e9+10;
const ll INF_LL = 1e18; //Be careful for overflow.
const int NONE = -1;
const int SUCCESSFUL = -2;

#define GOAL 123456780
//int numOfMove = -1; //?????°
ll numOfSearch = 0;

#define N_MAX 181440 //num of vertex or element
#define M_MAX 10000 //num of edge

int N;

struct d T[N_MAX+1]; //Binary Search Tree
int H = 0; //num of data in T[]. next new data will be placed on T[H]

queue<pii> Q; // <puzzle, sign>

void printInorder(int i) {
    if(i==NONE) return;
    
    printInorder(T[i].l);
    dout << " " << T[i].n;
    printInorder(T[i].r);
}
void printPreorder(int i) {
    if(i==NONE) return;
    
    dout << " " << T[i].n;
    printInorder(T[i].l);
    printInorder(T[i].r);
}
void print() {
    printInorder(0);
    dout << endl;
    printPreorder(0);
    dout << endl;
}

int find(int x, int i=0) {
    
    if(i==NONE) return NONE;
    if(T[i].n==x) return i;
    
    if(x < T[i].n) return find(x, T[i].l);
    else return find(x, T[i].r);
    
}


void insert(int x, int m, int i=0) { //insert x at T[i]

    if(T[i].n==INF) {
        T[i].n = x;
        T[i].m = m; //Binary Search Tree?????°????????¶????????????????????¨?????????????????????????????¶????????????????????¨???????????°????¨?????????????????????????????????¢?´¢?????´????????°???????????°??§????????????
        H++;
        return;
    }
    
    if(x < T[i].n) {
        if(T[i].l==NONE) T[i].l=H;
        insert(x, m, T[i].l);
    }
    else {
        if(T[i].r==NONE) T[i].r=H;
        insert(x, m, T[i].r);
    }
    
}

void puzzle_int2array(int puzzle, int p[]) {
    int digit = 1e8;
    rep(i,0,9) {
        p[i] = puzzle/digit;
        puzzle %= digit;
        digit /= 10;
    }
}

int puzzle_array2int(int p[]) {
    int puzzle = 0;
    int digit = 1e8;
    rep(i,0,9) {
        puzzle += p[i]*digit;
        digit /= 10;
    }
    
    return puzzle;
}





void display(int puzzle) {
    int digit = 1e8;
    
    for(int i=8; i>=0; i--) {
        dout << puzzle/digit << " ";
        if(i%3==0) dout << endl;
        
        puzzle %= digit;
        digit /= 10;
    }
}



void solve(int puzzle, int numOfMove=1) {
    
//    Q.push(make_pair(puzzle, numOfMove));
    Q.push(make_pair(puzzle, 1)); //??£????????°?????????????????¢?´¢??????????????°?????????????????¢?´¢
    Q.push(make_pair(GOAL, -1)); //???????????¢?´¢?????????GOAL????????\????????????
    
    while( !Q.empty() ) {
        
        puzzle = Q.front().first;
        numOfMove = Q.front().second; //??????????????¢?´¢?????´?????????????????°
        Q.pop();
        
        //??£?§£??????
        int index = find(puzzle);
        if( index!=NONE ) { //?????§???????????????
            if(numOfMove*T[index].m < 0) { //numOfMove ??¨ T[index].m ?????°?¬??????§????????°
                dout << abs(numOfMove) + abs(T[index].m) -2 << endl;
                return;
            }
            else { //????¬??????§????????°
                continue; //????????????
            }
        }
        
        insert(puzzle, numOfMove);

        
//        dout << "-----------------\n";
//        disp(++numOfSearch);
//        disp(numOfMove);
//        display(puzzle);
        

//??£?§£?????????????¨???§????????????????????£????????§?????????????????????
//        if(puzzle == GOAL) {
//            dout << numOfMove << endl;
//            return;
//        }
        
        int p[9];
        puzzle_int2array(puzzle,p);
        
        
        //find 0
        int zero=NONE;
        rep(i,0,9) {
            if( p[i] == 0 ) {
                zero = i;
                break;
            }
        }
        assert(zero!=NONE); //0 must be found
        
        
        //move 0 to 4 direction
        
        //?????°???????????????????????????1????????????
        if( numOfMove > 0) numOfMove++;
        else numOfMove--;
        
        int alt;
        
        alt = zero - 3;
        if(0<=alt && alt<=8) {
//            disp(-3);
            swap(p[zero], p[alt]);
            
            puzzle = puzzle_array2int(p);
            
            index = find(puzzle);
            if( index==NONE ) { //???????????????
                Q.push(make_pair(puzzle, numOfMove));
//                dout << "push to Q\n";
            }
            else if(numOfMove*T[index].m < 0) { //?????????????????£?????¨??????????????°?¬??????§????????°
                Q.push(make_pair(puzzle, numOfMove));
            }
            else { //????¬????????????????????????£????????????????????????
//                dout << "already found\n";
            }
            swap(p[zero], p[alt]);
        }
        
        alt = zero - 1;
        if(0<=alt && alt<=8 && zero%3!=0) { //0??????????????´?????????????????????
            //            disp(-1);
            swap(p[zero], p[alt]);
            
            puzzle = puzzle_array2int(p);
            
            index = find(puzzle);
            if( index==NONE ) { //???????????????
                Q.push(make_pair(puzzle, numOfMove));
                //                dout << "push to Q\n";
            }
            else if(numOfMove*T[index].m < 0) { //?????????????????£?????¨??????????????°?¬??????§????????°
                Q.push(make_pair(puzzle, numOfMove));
            }
            else { //????¬????????????????????????£????????????????????????
                //                dout << "already found\n";
            }
            swap(p[zero], p[alt]);
        }
        
        
        alt = zero + 1;
        if(0<=alt && alt<=8 && zero%3!=2) { //0??????????????´?????????????????????
            //            disp(1);
            swap(p[zero], p[alt]);
            
            puzzle = puzzle_array2int(p);
            
            index = find(puzzle);
            if( index==NONE ) { //???????????????
                Q.push(make_pair(puzzle, numOfMove));
                //                dout << "push to Q\n";
            }
            else if(numOfMove*T[index].m < 0) { //?????????????????£?????¨??????????????°?¬??????§????????°
                Q.push(make_pair(puzzle, numOfMove));
            }
            else { //????¬????????????????????????£????????????????????????
                //                dout << "already found\n";
            }
            swap(p[zero], p[alt]);
        }
        
        alt = zero + 3;
        if(0<=alt && alt<=8 ) {
            //            disp(3);
            swap(p[zero], p[alt]);
            
            puzzle = puzzle_array2int(p);
            
            index = find(puzzle);
            if( index==NONE ) { //???????????????
                Q.push(make_pair(puzzle, numOfMove));
                //                dout << "push to Q\n";
            }
            else if(numOfMove*T[index].m < 0) { //?????????????????£?????¨??????????????°?¬??????§????????°
                Q.push(make_pair(puzzle, numOfMove));
            }
            else { //????¬????????????????????????£????????????????????????
                //                dout << "already found\n";
            }
            swap(p[zero], p[alt]);
        }
        
    } //end of while-loop
    
}




int main() {
    
    //initialize
    rep(i,0,N_MAX+1) {
        T[i].n = INF;
        T[i].l = T[i].r = NONE;
    }
    
    int puzzle = 0;
    int digit = 1e8;

    int p;
    rep(i,0,9) {
            din >> p;
            puzzle += digit * p;
            digit /= 10;
    }
    
    
//    display(puzzle);
    
    solve(puzzle, 0);

    

    
    
    
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}

Measured memory_bytes: 6080