// ****************************************************************************
// C header
// ****************************************************************************
#include <cmath>
// ****************************************************************************
// C++ header
// ****************************************************************************
#include <iostream>
// ****************************************************************************
// STL library
// ****************************************************************************
#include <queue>
#include <set>
// ****************************************************************************
// MACRO
// ****************************************************************************
#define N       3
#define FINITE  123456780
// ****************************************************************************
// STRUCT
// ****************************************************************************
typedef struct _State {
    int v[N][N];
    int cnt;
    int x, y;
} State;
// ****************************************************************************
// PROTOTYPE
// ****************************************************************************
int hash ( int state[][N] );
int solve( int state[][N] );
// ****************************************************************************
// GLOBAL VARIABLE
// ****************************************************************************
std::set< int > hset;
// ****************************************************************************
// FUNCTIONS
// ****************************************************************************
int hash( int state[][N] ) {
    int res=0, k=8;
    for (int i=0; i<N; ++i) {
        for (int j=0;j<N; ++j) {
            res += state[i][j] * pow(10, k);
            --k;
        }
    }
    return res;
}

int solve( int state[][N] ) {
    int dx[] = {-1,  0,  1,  0},
        dy[] = { 0, -1,  0,  1};
    std::queue< State > que;
    while ( !que.empty() ) que.pop();
    State s;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            s.v[i][j] = state[i][j];
            if (state[i][j] == 0) {
                s.x = i;
                s.y = j;
            }
        }
    }
    s.cnt = 0;
    que.push( s );

    while ( !que.empty() ) {
        s = que.front();
        int h = hash( s.v );

        if ( h == FINITE ) break;

        if (hset.find( h ) == hset.end()) {
            hset.insert( h );

            for (int i=0; i<4; ++i) {
                int x=s.x+dx[i], y=s.y+dy[i];
                if (0<=x && x<N && 0<=y && y<N) {
                    State tmp = s;
                    std::swap( tmp.v[s.x][s.y], tmp.v[x][y] );
                    tmp.x = x;
                    tmp.y = y;
                    ++tmp.cnt;
                    que.push( tmp );
                }
            }
        }
        que.pop();
    }
    return que.front().cnt;
}
// ****************************************************************************
// MAIN FUNCTION
// ****************************************************************************
int main() {
    int state[N][N];
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            std::cin >> state[i][j];
        }
    }
    std::cout << solve( state ) << std::endl;
    return 0;
}



Measured memory_bytes: 13236