#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>

using namespace std;
#define N 3
#define N2 9

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r','u','l','d'};
int MDT[N2][N2];

struct Puzzle {
    int f[N2], space, MD;
    int cost;

    bool operator < (const Puzzle &p) const{
        for(int i=0; i<N2; i++){
            if(f[i]==p.f[i]) continue;
            return f[i] < p.f[i];
        }
        return false;
    }
};

struct State{
    Puzzle puzzle;
    int estimated;
    bool operator < (const State &s) const{
        return estimated > s.estimated;
    }
};

int getAllMD(Puzzle pz){
    int sum=0;
    for(int i=0; i<N2; i++){
        if(pz.f[i] == N2) continue;
        sum += MDT[i][pz.f[i]-1];
    }
    return sum;
}

int astar(Puzzle s){
    priority_queue<State> PQ;//優先順位付きキュー
    s.MD = getAllMD(s);//マンハッタン距離の初期値を計算
    s.cost = 0;//コスト値は最初は0
    //mapとはC++標準ライブラリに用意された平衡二分木.
    //要素の要素数に対する対数オーダーでの高速な検索が可能。内部で要素がソート状態で保持される
    //辞書みたいな使い方が多い
    //Puzzleがkey,boolがvalue
    map<Puzzle, bool> V;
    Puzzle u, v;
    State initial;//State構造体はパズルの情報とヒューリスティック値を計算
    initial.puzzle = s; //Stateのインスタンスを生成
    initial.estimated = getAllMD(s);//sのマンハッタン距離を計算して格納
    PQ.push(initial);//initialをキューにプッシュ

    while(!PQ.empty()){//PQが空でない間はループ 全てのキューに入っている要素を見る
        State st = PQ.top(); PQ.pop();//キューの要素をstに代入して削除
        u = st.puzzle; //stのメンバである盤面情報puzzleをuに代入

        if(u.MD == 0) return u.cost;//マンハッタン距離が0 -->解けた
        V[u] = true;//Vはmapで、Puzzleのインスタンスとtrue,falseを対応させる。

        int sx = u.space / N;//x座標計算
        int sy = u.space % N;//y座標計算

        for(int r=0; r<4; r++){ //4方向すべてを試す。
            int tx = sx + dx[r]; //x方向の遷移
            int ty = sy + dy[r]; //y方向の遷移
            if(tx<0 || ty<0 || tx>=N || ty>=N) continue;//移動後マスからはみ出した場合
            v = u;
            
            /*マンハッタン距離の差分を計算しつつ、ピースをスワップ*/
            //tx * N + tyは空白の位置。f配列はパズルのマスの値。v.f[tx * N + ty]はパズルの値
            //空白が移動する先(tx*N+ty)がもともとの数字があった場所なので、移動前のマンハッタン距離を引く
            v.MD -= MDT[tx * N + ty][v.f[tx * N + ty] - 1];
            //もともとの数字は空白があった場所に移動する。これによって増えるマンハッタン距離を足す。
            v.MD += MDT[sx * N + sy][v.f[tx * N + ty] - 1];

            swap(v.f[sx * N + sy], v.f[tx * N + ty]);//空白の位置をswap
            v.space = tx * N + ty;//swapしたので空白の位置を更新
            if(!V[v]){
                v.cost++;//swapしたので木の下に行ってコストが1増える
                State news;
                news.puzzle = v;
                news.estimated = v.cost + v.MD;//木の深さとマンハッタン距離を足してヒューリスティック値にする。
                PQ.push(news);
            }
        }
    }
    return -1;
}

int main(){
    //マンハッタン距離の計算
    for(int i=0; i<N2; i++){
        for(int j=0;j<N2;j++){
            //MDT[i][j] := 「1次元配列上の」位置iから位置jに移動させるとした時、
            //2次元配列上ではマンハッタン距離でどれくらい移動してるかを前計算
            //abs(i/N - j/N)は縦方向の距離の絶対値
            //abs(i%N - j%N)は横方向の距離の絶対値
            MDT[i][j] = abs(i/N-j/N) + abs(i%N-j%N);//マンハッタン距離
        }
    }
    Puzzle in;

    for(int i=0;i<N2;i++){
        cin >> in.f[i];
        if(in.f[i]==0){
            in.f[i] = N2;//空白の部分はN2(16)を代入
            in.space = i;//空白の位置を格納
        }
    }
    cout << astar(in) << endl;

    return 0;

}




Measured memory_bytes: 4580