#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define PSIZE 4
#define PPSIZE PSIZE * PSIZE
#define METHOD 0

using namespace std;

typedef enum Move {
    UP,
    DOWN,
    LEFT,
    RIGHT,
    NOMOVE
}Move;

int dist_table[PPSIZE][PPSIZE];

int mdist(int p1[]) {
    int dist = 0;
    int pi, num;
    for (int i = 0; i < PPSIZE; i++) {
        if (p1[i] == 0) continue;
        dist += dist_table[p1[i]-1][i];
    }
    return dist;
}

int hdist(string p) {
    int dist = 0;
    int j;
    for (int i = 0; i < PPSIZE; i++) {
        char c = p[i];
        if (c == '0') {
            continue;
        } else if (c >= '1' && c <= '9') {
            j = c - '1';
        } else {
            j = c - 'A' + 9;
        }
        if (i != j) dist += 1;
    }
    return dist;
}

int hdist2(int* p) {
    int dist = 0;
    int j;
    for (int i = 0; i < PPSIZE-1; i++) {
        if (i != p[i]-1) dist += 1;
    }
    return dist;
}

int dist_func(int* p, int method) {
    if (method == 0) return mdist(p);
    else return hdist2(p);
}

void swapInt(int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

bool movePuzzle(int* p, int &si, Move move) {
    if (move == UP) {
        if (si < PSIZE) return false;
        swapInt(p[si], p[si-PSIZE]);
        si = si - PSIZE;
    } else if (move == DOWN) {
        if (si >= PSIZE*(PSIZE-1)) return false;
        swapInt(p[si], p[si+PSIZE]);
        si = si + PSIZE;
    } else if (move == LEFT) {
        if (si % PSIZE == 0) return false;
        swapInt(p[si], p[si-1]);
        si = si - 1;
    } else if (move == RIGHT) {
        if (si % PSIZE == PSIZE-1) return false;
        swapInt(p[si], p[si+1]);
        si = si + 1;
    } else {
        return false;
    }
    return true;
}

void createDistTable() {
    for (int i = 0; i < PPSIZE; i++) {
        for (int j = 0; j < PPSIZE; j++) {
            dist_table[i][j] = abs(i / PSIZE - j / PSIZE) + abs(i % PSIZE - j % PSIZE);
        }
    }
}

int* copyPuzzle(int* p) {
    int* n = (int*)malloc(sizeof(int) * PPSIZE);
    memcpy(n, p, sizeof(int) * PPSIZE);
    return n;
}

bool dls(int depth, int* p, int si, Move prev, int limit_cost) {
    int dist = dist_func(p, METHOD);
    if (dist == 0) return true;
    if (dist + depth > limit_cost) return false;
    int next[PPSIZE];
    int next_si;
    for (int mi = 0; mi < NOMOVE; mi++) {
        Move move = (Move)mi;
        next_si = si;
        if (prev == UP && move == DOWN) continue;
        if (prev == DOWN && move == UP) continue;
        if (prev == LEFT && move == RIGHT) continue;
        if (prev == RIGHT && move == LEFT) continue;
        //next = copyPuzzle(p);
        memcpy(next, p, sizeof(int)*PPSIZE);
        if (!movePuzzle(next, next_si, move)) continue;
        if (dls(depth+1, next, next_si, move, limit_cost)) return true;
    }
    return false;
}

int main() {

    int start[PPSIZE];
    int space;
    int tmp;
    for (int i = 0; i < PSIZE; i++) {
        for (int j = 0; j < PSIZE; j++) {
            cin >> tmp;
            start[i*PSIZE+j] = (int)tmp;
            if (start[i*PSIZE+j] == 0) space = i*PSIZE+j;
        }
    }

    createDistTable();

    for (int limit_cost = dist_func(start, METHOD); limit_cost < 50; limit_cost++) {
        if (dls(0, start, space, NOMOVE, limit_cost)) {
            cout << limit_cost << endl;
            break;
        }
    }

    return 0;
}



Measured memory_bytes: 3104