#include <iostream>
#include <vector>
using namespace std;

constexpr int N = 4, N_2D = 16;
constexpr int MAX_LIMIT = 45;

struct Puzzle {
    int location[N_2D];
    int space;
    int MD; // マンハッタン距離の総距離
};

/**
 *  debug用
 */
void PrintPuzzle(int depth, const Puzzle &puzzle) {
	cout << "--------------------------\n";
	cout << "depth : " << depth << endl;
	for(int i = 0; i < N_2D; ++i){
		printf("%3d ", puzzle.location[i] == N_2D ? 0 : puzzle.location[i]);
		if(i % 4 == 3){
			cout << "\n";
		}
	}
	cout << "\nMD : " << puzzle.MD << "\n";
	cout << "--------------------------\n";
}

/**
 *  すべてのマスのマンハッタン距離の総和を計算する
 */
int CalcAllManhattanDistance(const Puzzle &puzzle, const vector<vector<int>> &manhattan_distance) {
    int res = 0;
    for(int i = 0; i < N_2D; ++i){
        if(puzzle.location[i] == N_2D){
            continue;
        }
        res += manhattan_distance[i][puzzle.location[i]-1];
    }
    return res;
}

/**
 *  深さ優先探索
 */
bool DFS(int depth, const vector<vector<int>> &manhattan_distance, int limit,
			Puzzle *state, int *ans, int prev = -MAX_LIMIT) {

    if((*state).MD == 0){
        *ans = depth;    // 一致したら終わり
        return true;
    }

    if((*state).MD + depth > limit){
        return false; // (limit)手以上必要
    }

    int sx = (*state).space / N;   // space x
    int sy = (*state).space % N;   // space y

    constexpr int dx[] = {0, 1, 0, -1};
    constexpr int dy[] = {1, 0, -1, 0};

    //PrintPuzzle(depth, *state);

    for(int i = 0; i < 4; ++i){
        int tx = sx + dx[i];    // transfer x
        int ty = sy + dy[i];    // transfer y

        if(tx < 0 || tx >= N || ty < 0 || ty >= N){
            continue;   // 移動先がパズルの枠を超える
        }
        if(abs(prev - i) == 2){
            continue;   // 前回と同じ位置
        }

        Puzzle next_state = *state;

        // spaceの位置を移動
        next_state.MD -= manhattan_distance[tx * N + ty][next_state.location[tx * N + ty] - 1];
        next_state.MD += manhattan_distance[sx * N + sy][next_state.location[tx * N + ty] - 1];
        swap(next_state.location[tx * N + ty], next_state.location[sx * N + sy]);
        next_state.space = tx * N + ty;

        if(DFS(depth + 1, manhattan_distance, limit, &next_state, ans, i)){
            return true;
        }
    }
    return false;
}

/**
 *  反復深化
 */
int IterativeDeepening(const Puzzle &puzzle, const vector<vector<int>> &manhattan_distance) {

    int ans = 0;
    Puzzle state;
    for(int limit = puzzle.MD; limit <= MAX_LIMIT; ++limit){
        state = puzzle;
        if(DFS(0, manhattan_distance,limit, &state, &ans)){
            return ans;
        }
    }
    return -1; // 45手以内ではできない
}

int main() {

    vector<vector<int>> manhattan_distance(N_2D, vector<int>(N_2D));  // ｉからｊまでの距離
    for (int i = 0; i < N_2D; ++i){
        for (int j = 0; j < N_2D; ++j){
            manhattan_distance[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
        }
    }

    Puzzle puzzle;
    for (int i = 0; i < N_2D; ++i){
        cin >> puzzle.location[i];
        if (puzzle.location[i] == 0){ // 0-indexにしたいのでスペースには16をいれる
            puzzle.location[i] = N_2D;
            puzzle.space = i;
        }
    }
    puzzle.MD = CalcAllManhattanDistance(puzzle, manhattan_distance);

    cout << IterativeDeepening(puzzle, manhattan_distance) << endl;

    return 0;
}



Measured memory_bytes: 3164