#include <iostream>
#include <istream>
#include <ostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <random>
#include <tuple>
#include <functional>

using namespace std;

inline int abs(int i) {return i > 0 ? i : -i;}

constexpr int W = 3;
constexpr int H = 3;
constexpr int WH = W * H;

enum class Direction {Left, Right, Up, Down};

struct Position
{
    int row;
    int col;
    bool slide(Direction d);
};

inline int pos2idx(const Position & pos) {return pos.row * W + pos.col;}

using Board = vector<int>;

int calc_MHD(Board & board);

Position find_blank(Board & board);


class Status
{
public:
    // ctor
    Status() = default;
    Status(Board & board_, Position & blank_): board{board_}, blank{blank_} {mhd = calc_MHD(board_);};
    Status(Board & board_): board{board_} {blank = find_blank(board_); mhd = calc_MHD(board_);};
    // copy, move ctor
    Status(const Status & status) = default;
    Status(Status && status) = default;
    // copy, move assignment
    Status& operator=(const Status & status) = default;
    Status& operator=(Status && status) = default;
    //detor
    ~Status() = default;
    
    friend istream & operator>>(istream & is, Status & st);
    
    bool operator==(const Status & rhs) const {return board == rhs.board;};
    bool operator<(const Status & rhs) const {return board < rhs.board;};
    bool operator>(const Status & rhs) const {return board > rhs.board;};
    
    bool slide(Direction d);
    
    int get_mhd() const {return mhd;};
    Board get_board() const {return board;};

private:
    Board board = {1, 2, 3, 4, 5, 6, 7, 8, 0};
    Position blank = {2, 2};
    int mhd = 0;
    void _update();
    void _update_after_slide(const Position & prev_blank);
};

istream & operator>>(istream & is, Board & board);

int solve(Status status);

////////////////////////////////////////////////
// main function
////////////////////////////////////////////////
int main()
{
    Status status;
    cin >> status;
    cout << solve(status) << endl;
    return 0;
}


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

int solve(Status status){
    priority_queue< pair<int, Status>, vector< pair<int, Status> >, greater< pair<int, Status> > > pq;
    map<Board, int> b2s;
    
    pq.emplace(0 + status.get_mhd(), status);
    b2s[status.get_board()] = 0;
    while (not pq.empty()){
        int p;
        Status st;
        tie(p, st) = pq.top();
        pq.pop();
        if (st.get_mhd() == 0) return p;
        int steps = p - st.get_mhd();
        auto bd = st.get_board();
        if (b2s[bd] < steps) continue;
        for (auto d : {Direction::Left, Direction::Right, Direction::Up, Direction::Down}){
            Status new_st{st};
            if (new_st.slide(d)){
                auto new_bd = new_st.get_board();
                auto it = b2s.find(new_bd);
                if (it == b2s.end() or it->second > steps + 1){
                    b2s[new_bd] = steps + 1;
                    pq.emplace(steps + 1 + new_st.get_mhd(), new_st);
                }
            }
        }
    }
    return -1;
}

int calc_MHD(Board & board){
    // Calculates the sum of Manhattan distances
    // from current position to goal position 
    // for all panels except blank (=0) panel. 
    int mhdist = 0;
    int src = 0;
    for (auto dst : board){
        if (dst == 0){
            ++src;
            continue;
        }
        dst = (dst + WH - 1) % WH;
        int drow = abs(src / W - dst / W);
        int dcol = abs(src % W - dst % W);
        mhdist += drow + dcol;
        ++src;
    }
    return mhdist;
}


Position find_blank(Board & board){
    // Find a blank (=0) panel on a board with width=W and height=H
    // and return its position (row, col).
    for(int i = 0; i != WH; ++i){
        if (board[i]) continue;
        return {i / W, i % W};
    }
}


istream & operator>>(istream & is, Board & board){
    for (int i = 0; i != WH; ++i){
        cin >> board[i];
    }
    return is;
}


istream & operator>>(istream & is, Status & st){
    is >> st.board;
    st._update();
    return is;
}

bool Position::slide(Direction d){
    switch(d){
        case Direction::Left:
            if (col <= 0) return false;
            --col;
            break;
        case Direction::Right:
            if (col >= W - 1) return false;
            ++col;
            break;
        case Direction::Up:
            if (row <= 0) return false;
            --row;
            break;
        case Direction::Down:
            if (row >= H - 1) return false;
            ++row;
            break;
    }
    return true;
}

bool Status::slide(Direction d){
    Position prev_blank = blank;
    if (blank.slide(d)){
        // post_process
        _update_after_slide(prev_blank);
        return true;
    }else{
        // can't slide
        return false;
    }
}

void Status::_update(){
    blank = find_blank(board);
    mhd = calc_MHD(board);
}

void Status::_update_after_slide(const Position & prev_blank){
    auto prev_idx = pos2idx(prev_blank);
    auto new_idx = pos2idx(blank);
    auto panel_val = board[new_idx];
    // update Manhattan disntance
    // panel_val has moved from prev_blank to blank.
    int row_final = (panel_val - 1) / W;
    int col_final = (panel_val - 1) % W;
    // subtract the Manhattan distance from the previous position of panel_val,
    // which is the same as the current position of blank, to the final position of panel_val.
    mhd -= abs(row_final - blank.row) + abs(col_final - blank.col);
    // add the Manhattan distance from the current position of panel_val,
    // which is the same as the previous position of blank, to the final position of panel_val.
    mhd += abs(row_final - prev_blank.row) + abs(col_final - prev_blank.col);
    
    // swap 0 and panel_val
    board[prev_idx] = panel_val;
    board[new_idx] = 0;
}

Measured memory_bytes: 4652