/**
 * @brief 15パズル問題を扱う
 *
 * @date 2016/02/29
 */



//****************************************
// 必要なヘッダファイルのインクルード
//****************************************

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <limits>



//****************************************
// 型シノニム
//****************************************

using array1D = std::vector<int>;
using array2D = std::vector<array1D>;



//****************************************
// 大域変数の定義
//****************************************

static const int N = 4;     /**< 4x4の盤面を考える */
static const int NN = 16;   /**< 4x4 = 16 */

static const array1D dx = { -1,   0,   1,   0, };  /**< 方向ベクトルのx成分 */
static const array1D dy = {  0,  -1,   0,   1, };  /**< 方向ベクトルのy成分 */
static const char dir[] = { 'l', 'u', 'r', 'd',};  /**< 方向ベクトル */

static const int MAXDEPTH = 50;    /**< 再帰の深さ制限 */

array2D g_dist(NN, array1D(NN));    /**< マンハッタン距離を格納するテーブルで(駒の種類x駒の位置)を表す */
array1D g_path(MAXDEPTH);           /**< 最終状態までの手 */



//****************************************
// 構造体の定義
//****************************************

struct puzzle {
    array1D state;  /**< パズルの状態 */
    int space;      /**< 空いているパネルの位置 */
    int h;          /**< 各パネルにおける最終状態までのマンハッタン距離の総和 */

    /**< @brief コンストラクタ */
    puzzle() : state(NN), h(0) { }

    /**< @brief []演算子オーバーロード */
    int& operator [] (std::size_t i) { return state[i]; }
};



//****************************************
// 関数の定義
//****************************************

/**< @brief 各パネルにおける最終状態までのマンハッタン距離の総和を取得する */
int heuristic(puzzle& p) {
    int h = 0;
    for (int i = 0; i < NN; i++) {
        if (p[i] == NN) { continue; }
        h += g_dist[i][p[i] - 1];
    }
    return h;
}

/**< @brief マンハッタン距離の計算を行い、テーブルの初期化を行う */
void inittbl(array2D& dist)
{
    for (int i = 0; i < NN; i++) {
        for (int j = 0; j < NN; j++) {
            dist[i][j] = abs(i % N - j % N) + abs(i / N - j / N);
        }
    }
}


/**
 * @brief パズルの状態uを訪問する
 */
bool visit(puzzle& u, int plyDepth, int curDir, int limit)
{
    // u.h = 0ならば、パズルは最終状態へ達した
    if (u.h == 0) { return true; }
    // 現在の深さにヒューリスティック値を加算した値がlimitを超えた場合、枝のカットを行う
    if (plyDepth + u.h > limit) { return false; }
    
    // 現在空いているパネルの座標を取得
    int srcX = u.space % N;
    int srcY = u.space / N;
    puzzle v;
    // 左、上、右、下方向の順にループをまわす
    for (int nextDir = 0; nextDir < 4; nextDir++) {
        int dstX = srcX + dx[nextDir];
        int dstY = srcY + dy[nextDir];
        // パズルの範囲外となる場合は、隣接しないとみなす
        if (dstX < 0 || dstX >= N || dstY < 0 || dstY >= N) { continue; }
        // 向きが逆方向の場合、調べる必要がない
        if ((std::max(curDir, nextDir) - std::min(curDir, nextDir)) == 2) { continue; }
        // 以下、uの隣接リストに属するパズルの状態vを考える
        v = u;
        int dst = dstY * N + dstX;
        // マンハッタン距離の更新
        v.h -= g_dist[dst][u[dst] - 1];
        v.h += g_dist[u.space][u[dst] - 1];
        // ピースの交換
        std::swap(v[dst], v[u.space]);
        // 空きパネルの更新
        v.space = dst;
        // 再帰的にvを訪問する
        if (visit(v, plyDepth + 1, nextDir, limit)) { g_path[plyDepth] = dir[nextDir]; return true; }
    }
    return false;
}

/**
 * @brief 反復深化(Iterative Deeping)A*アルゴリズムによって15パズルを解く
 * @param puzzle s パズルの始点s
 */
std::string idastar(puzzle& s)
{
    // ゲーム初期状態のマンハッタン距離を計算する
    s.h = heuristic(s);
    // 深さの制限を増加させていく(反復深化)
    for (int limit = s.h; limit <= MAXDEPTH; limit++) {
        puzzle _s = s;
        // 深さ制限探索を行い、解が存在すれば、それが最短手である
        if (visit(_s, 0, std::numeric_limits<int>::min(), limit)) {
            std::string path = "";
            for (int i = 0; i < limit; i++) { path += dir[g_path[i]]; }
            return path;
        }
    }
    std::cout << "unresolvale" << std::endl;
    return "unresolvable";
}


int main()
{
    using namespace std;
    
    
    puzzle p;
    inittbl(g_dist);  // マンハッタン距離を格納するテーブルを用意
    for (int i = 0; i < NN; i++) {
        cin >> p[i];
        if (p[i] == 0) {
            p[i] = NN;
            p.space = i;
        }
    }
    string path = idastar(p);
    cout << path.size() << endl;

    return 0;
}

Measured memory_bytes: 3204