#include <bits/stdc++.h>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define INF INT_MAX/3
#define N 4
typedef pair<int, int> P;

struct State {
    int g, h;
    string state;
    P blank;
    string path;
    bool operator<(const State &a) const {
        return g + h > a.g + a.h;
    }
};

int d[5] = {-1, 0, 1, 0, -1};
string r[4] = {"D", "R", "U", "L"};
string ans_str = "";
int ans[N][N], puzzle0[N][N], puzzle1[N][N];
set<string> s;
priority_queue<State> next_state;
string path;

bool range(int y, int x) {return 0 <= y && y < N && 0 <= x && x < N;}

int h2_dfs(int boundary, State state, int from) {
    int find = -1;
    s.insert(state.state); // visited

    P blank = state.blank;
    rep(i, 4) {
        if (from == (i + 2) % 4) continue;
        int y = d[i] + blank.first, x = d[i + 1] + blank.second; // next blank position
        if (range(y, x)) { // can be replaced
            string tmp = state.state; // next state (string)
            int p = blank.first * N + blank.second, q = y * N + x;
            if (N < 4) swap(tmp[p], tmp[q]);
            else swap(tmp[2 * p], tmp[2 * q]), swap(tmp[2 * p + 1], tmp[2 * q + 1]);

            int num;
            if (N < 4) num = state.state[q] - '1';
            else num = stoi(state.state.substr(2 * q, 2)) - 1;
            // calcurate manhattan distance
            int manhattan = state.h - ((abs(num / N - y) + abs(num % N - x)))
            + (abs(num / N - blank.first) + abs(num % N - blank.second));

            if (manhattan == 0) { // answer
                find = state.g + 1;
                path = state.path + r[i];
                break;
            }

            if (state.g + 1 + manhattan > boundary) continue; // estimate value is over boundary
            find = h2_dfs(boundary, State{state.g + 1, manhattan, tmp, P(y, x), state.path + r[i]}, i);
            if (find != -1) break;
        }
    }
    return find;
}

int ids_h2(string state, int manhattan, P blank) {
    int i = manhattan, find = -1;
    while(find == -1 && i < 81) {
        s.clear();
        find = h2_dfs(i, State{0, manhattan, state, blank, ""}, -1);
        i++;
    }
    return find;
}

int main(){
    // create answer's numbers
    iota(ans[0], ans[0] + N * N, 1);
    ans[N - 1][N - 1] = 0;
    // create number
    iota(puzzle0[0], puzzle0[0] + N * N, 0);
    rep(i, N)rep(j, N) cin >> puzzle0[i][j];

    string state = "";
    P blank;
    int manhattan = 0, wrong_place = 0;
    rep(i, N)rep(j, N) {
        // cout << puzzle0[i][j] << ((j % N == N - 1) ? "\n" : "\t");

        if (N * N - 1 > 9 && puzzle0[i][j] < 10) state += "0";
        state += to_string(puzzle0[i][j]);
        if (N * N - 1 > 9 && ans[i][j] < 10) ans_str += "0";
        ans_str += to_string(ans[i][j]);

        if(puzzle0[i][j] == 0) blank = P(i, j);
        else {
            int num = puzzle0[i][j] - 1;
            manhattan += (abs(num / N - i) + abs(num % N - j));
            if (puzzle0[i][j] != ans[i][j]) wrong_place++;
        }
    }

    if (manhattan == 0) { // the answer
        cout << 0 << endl;
    } else {
        int steps;
        next_state.push(State{0, wrong_place, state, blank, ""});
        steps = ids_h2(state, manhattan, blank);
        cout << steps << endl;
    }
    return 0;
}

Measured memory_bytes: 48764