#include <stdio.h>

#define true 1
#define false 0

#define MAX 4
#define INF 100000000

#define abs(a) (((a) < 0) ? (-1*a) : (a))
#define p(x, y) ((MAX * x) + y)

int limit;
int shortest = INF;
int count;
int puzzle[MAX * MAX];
int road[50][MAX * MAX];

void swap(int *x, int *y) {
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

int history(int depth) {
    int i, cnt;
    if (depth < 2) return -1;

    cnt = (MAX * MAX) - 1;
    for (i = 1; i < (MAX * MAX); i++) {
        if (puzzle[i - 1] == road[depth-2][i - 1]) {
            cnt--;
        }
    }
    if (cnt == 0) return cnt;
    return cnt;
}

int check() {
    int i, cnt;

    cnt = (MAX * MAX) - 1;
    for (i = 1; i < (MAX * MAX); i++) {
        if (puzzle[i - 1] == i) {
            cnt--;
        }
    }
    return cnt;
}

void sIndex(int key, int *x, int *y) {
    int i, j;
    for (i = 0; i < MAX; i++) {
        for (j = 0; j < MAX; j++) {
            if (key == puzzle[p(i, j)]){
                *x = i;
                *y = j;
            }
        }
    }
}

int heuri() {
    int i, x, y;
    int sum = 0;

    for (i = 1; i < (MAX * MAX); i++) {
        sIndex(i, &x, &y);
        sum += abs((((i-1) / MAX) - x)) + abs((((i-1) % MAX) - y));
    }

    return sum;
}

int up(int i, int *dir) {
    *dir = i - MAX;
    if (*dir >= 0) { return true; }
    else return false;
}

int down(int i, int *dir) {
    *dir = i + MAX;
    if (*dir < (MAX * MAX)) { return true; }
    else return false;
}

int left(int i, int *dir) {
    *dir = i - 1;
    if ((i % MAX != 0)) { return true; }
    else return false;
}

int right(int i, int *dir) {
    *dir = i + 1;
    if ((i + 1) % MAX != 0) { return true; }
    else return false;
}

void disp(int depth) {
    int i;
    if (depth < 0) return;

    for (i = 0; i < (MAX * MAX); i++) {
        if ((i % MAX) == 0) printf("\n");
        printf("%d ", road[depth][i]);
    }
    printf("\n");
    disp(depth - 1);
}

void cp(int depth) {
    int i;
    for (i = 0; i < (MAX * MAX); i++) {
        road[depth][i] = puzzle[i];
    }
}

void dfs(int depth, int pos) {
    int dir;
    int h = check();
    cp(depth);
    count++;

    if (depth + heuri() >= limit || history(depth) == 0) {
        return;
    }
    if (h == 0) {
        if (shortest > depth) {
            shortest = depth;
            limit = depth;
            //printf(">> %d\n", depth);
        }
        //disp(depth);
        return;
    }

    if (up(pos, &dir)) {
        swap(&puzzle[pos], &puzzle[dir]);
        dfs(depth+1, dir);
        swap(&puzzle[pos], &puzzle[dir]);
    }
    if (down(pos, &dir)) {
        swap(&puzzle[pos], &puzzle[dir]);
        dfs(depth+1, dir);
        swap(&puzzle[pos], &puzzle[dir]);
    }
    if (right(pos, &dir)) {
        swap(&puzzle[pos], &puzzle[dir]);
        dfs(depth+1, dir);
        swap(&puzzle[pos], &puzzle[dir]);
    }
    if (left(pos, &dir)) {
        swap(&puzzle[pos], &puzzle[dir]);
        dfs(depth+1, dir);
        swap(&puzzle[pos], &puzzle[dir]);
    }
}

int  main() {
    int i, pos;

    for (i = 0; i < (MAX * MAX); i++) {
        scanf("%d", &puzzle[i]);
        if (puzzle[i] == 0) {
            pos = i;
        }
    }
    limit = (check() + 1) * 4;
    if (limit >= 45) {
        limit = 46;
    }
    //printf("heuri >> %d\n", heuri());

    dfs(0, pos);

    if (shortest != INF) {
        printf("%d\n", shortest);
        //printf("count >> %d\n", count);
    } else {
        printf(">> not Solve limit-> %d, %d\n", limit, count);
        disp(limit);
    }

    return 0;
}


Measured memory_bytes: 2148