// 8パズル
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>

#include<vector>
#include<map>
#include<queue>

using namespace std;

//const int PUZZLE_NUM = 9;

// パネルの移動方向の定義
const int LOW = 1;
const int UP = 2;
const int LEFT = 3;
const int RIGHT = 4;

// 目標の状態 ( 0x12345678 を 10 進数に変換した値 )
int Target = 305419896;

const int PANEL_NUM = 8;
// 1 〜 8 までの和
const int ALL_SUM = 36;

// 並び替えの状態を格納するキュー
// 第1要素 : 検索する数値, 第2要素 : 並び替えた回数
queue<pair<int, int>> q_P;
// 探索済みのパネルの状態を格納しておくマップ
map<int, bool> Map_V;

// -------------------------------
// パズルのパネルを操作するためのクラス
// -------------------------------
class PuzzleOperation
{

    public:

        // パネルの並びを16進数に変換して格納する変数
        int panel;
        // パネル内のゼロの位置
        int zeroPos;
        // panel を分解した状態を保持する配列
        //int ary_panel[PANEL_NUM];
        // 8 個のパネルに入っていない数
        int remainNum;
        // 並び替えの回数
        int sortNum;

    // コンストラクタ
    PuzzleOperation()
    {
        panel = 0;
        zeroPos = 0;
        remainNum = 0;
        sortNum = 0;
    }

    // コピーコンストラクタ
    PuzzleOperation(const PuzzleOperation& p)
    {
        panel = p.panel;
        zeroPos = p.zeroPos;
        remainNum = p.remainNum;
        sortNum = p.sortNum;

        //cout << "コピーコンストラクタが呼ばれました" << endl;
    }

    // デストラクタ
    ~PuzzleOperation()
    {
        //cout << "デストラクタが呼ばれました" << endl;
    }

    // --------------------------------------------------
    // map のキーである PuzzleOperation クラスをキー順に並べるための定義
    // --------------------------------------------------
    bool operator < (const PuzzleOperation &p ) const
    {

        if( panel > p.panel )
        {
            return true;
        }
        else
        {
            return false;
        }

    }

    // ゴールに到達したかを判定する関数
    bool reachGoal(int p)
    {
        if( p != Target )
        {
            return false;
        }

        return true;
    }

    // panel に設定された数値から正解を求める
    // 計算値 : num の中で 4bit がゼロとなっている位置 ( zeroPos )
    //       : 8個の配列要素に含まれていない数 ( remainNum )
    // 戻り値 : 並び替えの回数
    bool panelMove()
    {
        int x, y;
        bool retX = false, retY = false;

        int tmp = panel;
        int bitNum;

        // 最初に 1 〜 8 までの和を入れておいて, 不足している数を求める
        remainNum = ALL_SUM;
        // 配列の 9 番目にゼロが存在することを考慮しておく
        // ( 要素数としては, 8 番目 )
        zeroPos = 8;

        for(int i = PANEL_NUM - 1; i >= 0; i--)
        {
            bitNum = tmp & 0xF;
            // 配列の 8 要素に入ってない値を求める
            remainNum -= bitNum;

            if( bitNum == 0 )
            {
                // ゼロ位置の設定
                zeroPos = i;
            }

            tmp = tmp >> 4;
        }

        // ゼロの位置から x, y 座標に変換する
        x = zeroPos / 3;
        y = zeroPos % 3;

        // -----------------
        // パネルを移動させる
        // -----------------
        retX = moveX(x, y);
        retY = moveY(x, y);

        if( retX == true || retY == true )
        {
            // パネルが目標の状態に到達した
            return true;
        }

        return false;
    }

    // 指定位置のパネルとゼロ位置のパネルの入れ替え操作をする処理
    bool panelReplacement(int movePos)
    {

        bool ret = false;
        int movePanel, moveNum, sortCount;

        // 移動操作はコピーしたもので実施する
        movePanel = panel;
        sortCount = sortNum;
        moveNum = 0;

        if( movePos < PANEL_NUM )
        {
            // -------------------------
            // 8 以内ならそのまま入れ替える
            // -------------------------

            // 移動する値まで, 4ビット単位でビットシフトする
            moveNum = movePanel >> ( 4 * ( ( PANEL_NUM - 1 ) - movePos ) );
            // 移動する値を抜き出す
            moveNum = moveNum & 0xF;
        }
        else
        {
            // 9 個目の要素なら, remainNum を入れておく
            moveNum = remainNum;
        }

        // -----▼▼▼ ゼロの位置に移動する値を入れる処理　▼▼▼-----

        if( zeroPos != 8 )
        {
            // 配列要素の 8 番目にゼロがあった場合は配列の圏外になるので何もしない

            // 移動する値を, 移動する位置まで, 4ビット単位でビットシフトする
            moveNum = moveNum << ( 4 * ( ( PANEL_NUM - 1 ) - zeroPos ) );
            // 移動する値をゼロの位置に入れる
            movePanel = movePanel | moveNum;
        }

        // -----▲▲▲ ゼロの位置に移動する値を入れる処理　▲▲▲-----

        // -----▼▼▼ 移動させた箇所をゼロに落とす処理　▼▼▼-----

        if( movePos < PANEL_NUM )
        {
            int zeroNum = 0xF;

            // ゼロの入る位置まで, 4ビット単位でビットシフトする
            zeroNum = zeroNum << ( 4 * ( ( PANEL_NUM - 1 ) - movePos ) );
            // ビット反転する
            zeroNum = ~zeroNum;
            // ゼロを設定する
            movePanel = movePanel & zeroNum;
        }

        // -----▲▲▲ 移動させた箇所をゼロに落とす処理　▲▲▲-----

        // 配列から数値へ統合する
        //copy.numIntegration();

        // 入れ替え回数をインクリメントする
        sortCount++;

        if( reachGoal(movePanel) == false )
        {
            // 並び替えたものをキューに入れ直す
            if( searchPanelStatus(movePanel) == true )
            {
                // 未検索の数値のみキューにプッシュする
                q_P.push(make_pair(movePanel, sortCount));
            }
        }
        else
        {
            ret = true;
        }

        return ret;
    }

    // ------------------
    // x 方向のパネルを移動
    // ------------------
    // x : パネル位置の x 座標
    // y : パネル位置の y 座標
    // 戻り値 : true - 目標到達, false : 目標に到達していない
    bool moveX(int x, int y)
    {
        bool ret = false;

        // 関数コール後の x は値が変わるので元の値を覚えておく
        int nowX = x;

        switch (x)
        {
            case 0:
                // 下のパネルと交換
                panelShift_X(LOW, x);
                ret = panelSwap(x, y);
                break;

            case 1:

                // 上のパネルと交換
                panelShift_X(UP, x);
                ret = panelSwap(x, y);

                if( ret == false )
                {
                    x = nowX;

                    // 下のパネルと交換
                    panelShift_X(LOW, x);
                    ret = panelSwap(x, y);
                }

                break;

            case 2:
                // 上のパネルと交換
                panelShift_X(UP, x);
                ret = panelSwap(x, y);

                break;
        }

        return ret;
    }

    // ------------------
    // y 方向のパネルを移動
    // ------------------
    // puz : パネルの状態を保持する配列
    // x : パネル位置の x 座標
    // y : パネル位置の y 座標
    // 戻り値 : true - 目標到達, false : 目標に到達していない
    bool moveY(int x, int y)
    {
        bool ret = false;

        // 関数コール後の y は値が変わるので元の値を覚えておく
        int nowY = y;

        switch (y)
        {
            case 0:
                // 右のパネルと交換
                panelShift_Y(RIGHT, y);
                ret = panelSwap(x, y);
                break;

            case 1:

                // 左のパネルと交換
                panelShift_Y(LEFT, y);
                ret = panelSwap(x, y);

                if( ret == false )
                {
                    y = nowY;

                    // 右のパネルと交換
                    panelShift_Y(RIGHT, y);
                    ret = panelSwap(x, y);
                }

                break;

            case 2:
                // 左のパネルと交換
                panelShift_Y(LEFT, y);
                ret = panelSwap(x, y);

                break;
        }

        return ret;
    }

    // -------------------------------------
    // 移動後のパネルが目標に到達しているかを確認
    // -------------------------------------
    // puz : パネルの状態を保持する配列
    // x : パネル位置の x 座標
    // y : パネル位置の y 座標
    // 戻り値 : true - 目標到達, false : 目標に到達していない
    bool panelSwap(int x, int y)
    {
        bool ret = false;
        int movePos;

        // 移動させる前に複製を作っておく
        //PuzzleOperation copy = puz;

        // 座標から配列の要素No.へ変換する
        movePos = calcArrayNum(x, y);
        // 数値を入れ替える
        ret = panelReplacement(movePos);

        return ret;
    }

    // x, y 座標から配列の要素数へ変換する関数
    int calcArrayNum(int x, int y)
    {
        return 3 * x + y;
    }

    // パネルの移動後の X 座標を計算する関数
    void panelShift_X(int moveNum, int &x)
    {
        switch ( moveNum )
        {
            case UP:
                x = x - 1;
                break;

            case LOW:
                x = x + 1;
                break;

            default:
                // x をそのまま返す
                break;
        }
    }

    // パネルの移動後の Y 座標を計算する関数
    void panelShift_Y(int moveNum, int &y)
    {
        switch ( moveNum )
        {
            case LEFT:
                y = y - 1;
                break;

            case RIGHT:
                y = y + 1;
                break;

            default:
            // y をそのまま返す
                break;
        }
    }

    // 検索したパネルの並びを記憶して、過去のパネル状態との比較もする
    // puz   : 整数値に置き換えるパネルの状態
    // 戻り値 : true - 新しいパターン, false : 検索済みのパターン
    bool searchPanelStatus(int p)
    {
        int ret = false;

        if( !Map_V[p] )
        {
            // --- 指定値が未検索の時 ---

            // 検索済みであることを記憶する
            Map_V[p] = true;
            ret = true;
        }

        return ret;

    }

};

// ----------------
// 8パズルを解く関数
// ----------------
// 戻り値 : パネルの移動回数
int solveEightPuzzle()
{
    int count = 0;

    while( !q_P.empty() )
    {
        pair<int, int> q_element;
        PuzzleOperation puz;

        q_element = q_P.front();
        q_P.pop();

        // キューから取り出した値を設定する
        puz.panel = q_element.first;
        puz.sortNum = q_element.second;

        // 整数値からパネルの並びへと分割する
        if( puz.panelMove() == true )
        {
            // puz の状態は正解の一つ前の状態なので, 最終的な回数として1を足しておく
            count = puz.sortNum + 1;
            break;
        }
    }

    return count;
}

int main(void)
{

    int count = 0;
    int panelCond = 0;

    PuzzleOperation puz;

    int ary_panel[PANEL_NUM];

    // 初期状態を設定する
    for(int i = 0; i < PANEL_NUM; i++)
    {
        cin >> ary_panel[i];
    }

    // 数値に変換する
    // 8個の配列要素から, panel に数値を設定する
    for(int i = 0; i < PANEL_NUM; i++)
    {
        // 4bit 左にシフトする
        panelCond = panelCond << 4;
        // 数値に変換する
        panelCond += ary_panel[i] & 0xF;
    }

    // 初期状態の設定
    puz.panel = panelCond;
    puz.sortNum = 0;

    q_P.push(make_pair(puz.panel, 0));
    puz.searchPanelStatus(puz.panel);

    if( puz.reachGoal(panelCond) == false )
    {
        // 最初の入力が正解で無ければ, 探索を開始する
        count = solveEightPuzzle();
    }

    printf("%d\n", count);

    return 0;
}



Measured memory_bytes: 11724