#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
#define UP 0
#define DOWN 2
#define LEFT 1
#define RIGHT 3
#define DEBUG 0
#define true 1
#define false 0



int up[2] = {-1,0};
int down[2] = {1,0};
int left[2] = {0,-1};
int right[2] = {0,1};

int targetPoints[SIZE*SIZE][2] ;

int cost;
int blank_row,blank_column;
int tState[SIZE][SIZE];

void get_matrix(int tmp[][SIZE]);
void print_matrix(int tmp[][SIZE]);
void targetPoints_constructor(int state[][SIZE]);
int getHeuristic(int tmp[][SIZE]);
int checkState(int state[][SIZE]);
int solve(int state[][SIZE], int blank_row, int blank_column, int dep, int d, int h);

int main(){
    int step  = 0;
    int sState[SIZE][SIZE];
    int conut = 0;
    int x;
    int y;
    int i;
    int j;

    for(x = 0; x < SIZE ; x++){
        for(y = 0; y<SIZE; y++){
            tState[x][y] = x*SIZE + y + 1;
        }
    }
    tState[SIZE-1][SIZE-1] = 0;

    if(DEBUG)print_matrix(tState);

    get_matrix(sState);

    if(DEBUG)print_matrix(sState);
    targetPoints_constructor(sState);

    if(checkState(sState)){
        printf("%d\n",step);
    }else{
        j = getHeuristic(sState);
        i = -1;

        for(cost = j; ;cost++){
            if(solve(sState, blank_row, blank_column, 0 , i, j)){
                break;
            }
        }
        printf("%d\n",cost);
    }
}

int solve(int state[][SIZE], int blank_row, int blank_column, int dep, int d, int h){
    int h1;
    int isSovled = checkState(state);
    if(isSovled){
        return true;
    }
    if(dep == cost){
        return false;
    }

    int blank_row1;
    int blank_column1;
    int state2[SIZE][SIZE];
    int direction = 0;
    int i;
    int j;

    for(direction=0;direction<4;direction++) {
        for(i=0;i<SIZE;i++) {
            for(j=0;j<SIZE;j++) {
                state2[i][j] = state[i][j];
            }
        }


            if(direction != d && (d%2 == direction%2)) {
                continue;
            }

            if(direction == UP) {
                blank_row1 = blank_row + up[0];
                blank_column1 = blank_column + up[1];
            } else if(direction == DOWN) {
                blank_row1 = blank_row + down[0];
                blank_column1 = blank_column + down[1];
            } else if(direction == LEFT) {
                blank_row1 = blank_row + left[0];
                blank_column1 = blank_column + left[1];
            } else {
                blank_row1 = blank_row + right[0];
                blank_column1 = blank_column + right[1];
            }


            if(blank_column1 < 0 || blank_column1 == SIZE
                    || blank_row1 < 0 || blank_row1 == SIZE) {
                continue ;
            }

 
            state2[blank_row][blank_column] = state2[blank_row1][blank_column1];
            state2[blank_row1][blank_column1] = 0;


            if(direction == DOWN && blank_row1
                    > targetPoints[state[blank_row1][blank_column1]][0]) {
                h1 = h - 1;
            } else if(direction == UP && blank_row1
                    < targetPoints[state[blank_row1][blank_column1]][0]){
                h1 = h - 1;
            } else if(direction == RIGHT && blank_column1
                    > targetPoints[state[blank_row1][blank_column1]][1]) {
                h1 = h - 1;
            } else if(direction == LEFT && blank_column1
                    < targetPoints[state[blank_row1][blank_column1]][1]) {
                h1 = h - 1;
            } else {
                h1 = h + 1;
            }


            if(h1+dep+1> cost) {
                continue;
            }

            if(solve(state2, blank_row1, blank_column1, dep+1, direction, h1)) {
                return true;
            }
        }
        return false;



}

int checkState(int state[][SIZE]){
    int b = true;
    int i;
    int j;
    for(int i = 0;i<SIZE;i++) {
        for (int j = 0; j < SIZE; j++) {
            if (!(state[i][j] == tState[i][j])) {
                b = false;
            }
        }
    }
    return b;
}

int getHeuristic(int tmp[][SIZE]){
    int i;
    int i2;
    int j;
    int j2;
    int ans = 0;
    int value = 0;
    int gap = 0;
    for(i = 0; i < SIZE; i++){
        for(j = 0; j < SIZE; j++){
            if(tmp[i][j] == 0)
                continue;

            if(tmp[i][j] != (i*SIZE+j+1)){
                value = tmp[i][j];
                i2 = j2 = gap = 0 ;
                while(value >SIZE){
                    value -= SIZE;
                    i2++;
                }
                j2 = value -1;

                gap += abs(i2-i);  
                gap += abs(j2 -j);
                //printf("h2 : i = %d   j = %d  gap= %d   value = %d  i2 = %d   j2 = %d \n",i,j,gap,tmp[i][j],i2,j2);
                ans += gap;
            }
                
        }
    }
    return ans;
}

void targetPoints_constructor(int state[][SIZE]){
    int i;
    int j;
    for(i=0;i<SIZE;i++) {
        for(j=0;j<SIZE;j++) {
               if(state[i][j] == 0) {
                   blank_row = i;
                   blank_column = j;
                   break;
               }
           }
    }
    if(DEBUG)printf("Xz = %d, Yz = %d\n",blank_row,blank_column);
    for(i=0;i<SIZE;i++) {
        for(j=0;j<SIZE;j++) {
            targetPoints[tState[i][j]][0] = i;
            targetPoints[tState[i][j]][1] = j;
        }
    }
}


void get_matrix(int tmp[][SIZE]){
    int i;
    int j;
    for(i = 0; i < SIZE; i++){
        for(j = 0; j < SIZE; j++){
            scanf("%d", &tmp[i][j]);
        }
    }
    return;
}
void print_matrix(int tmp[][SIZE]){
    int i;
    int j;
    for(i = 0; i < SIZE; i++){
        printf("%d",tmp[i][0]);
        for(j = 1; j < SIZE; j++){
            printf(" %d", tmp[i][j]);
        }
        printf("\n");
    }
    return;
}


Measured memory_bytes: 2104