#include<stdio.h>
#include<vector>
#include<cstdlib>
#include<utility>
using namespace std;

class State{
public:
    vector<vector<int>> puzzle;
    int zero_col, zero_row, prev_zero_col, prev_zero_row;
    int edge_len, heuristic;
    State(vector<vector<int>>& arr, const int& zc, const int& zr, const int& pzc, const int& pzr, const int& h): puzzle(arr), zero_col(zc), zero_row(zr), prev_zero_col(pzc), prev_zero_row(pzr), heuristic(h) {
        edge_len = arr.size();
    }
    int get_manhattan_diff(const int& new_zero_col, const int& new_zero_row){
        int diff = 0;
        diff += abs((puzzle[new_zero_row][new_zero_col]-1)/edge_len - zero_row) + abs((puzzle[new_zero_row][new_zero_col]-1)%edge_len - zero_col) - abs((puzzle[new_zero_row][new_zero_col]-1)/edge_len - new_zero_row) - abs((puzzle[new_zero_row][new_zero_col]-1)%edge_len - new_zero_col);
        return diff;
    }
    vector<State> get_next_states(){
        vector<State> res;    
        vector<vector<int>> tmp;
        int diff;
        if(zero_col+1 < edge_len && prev_zero_col != zero_col+1){
            diff = get_manhattan_diff(zero_col+1, zero_row);
            tmp = puzzle;
            swap(tmp[zero_row][zero_col], tmp[zero_row][zero_col+1]);
            res.push_back(State(tmp, zero_col+1, zero_row, zero_col, zero_row, heuristic + diff));
        }
        if(zero_col-1 >= 0 && prev_zero_col != zero_col-1){
            diff = get_manhattan_diff(zero_col-1, zero_row);
            tmp = puzzle;
            swap(tmp[zero_row][zero_col], tmp[zero_row][zero_col-1]);
            res.push_back(State(tmp, zero_col-1, zero_row, zero_col, zero_row, heuristic + diff));
        }
        if(zero_row+1 < edge_len && prev_zero_row != zero_row+1){
            diff = get_manhattan_diff(zero_col, zero_row+1);
            tmp = puzzle;
            swap(tmp[zero_row][zero_col], tmp[zero_row+1][zero_col]);
            res.push_back(State(tmp, zero_col, zero_row+1, zero_col, zero_row, heuristic + diff));
        }
        if(zero_row-1 >= 0 && prev_zero_row != zero_row-1){
            diff = get_manhattan_diff(zero_col, zero_row-1);
            tmp = puzzle;
            swap(tmp[zero_row][zero_col], tmp[zero_row-1][zero_col]);
            res.push_back(State(tmp, zero_col, zero_row-1, zero_col, zero_row, heuristic + diff));
        }
        return res;
    }
};

int get_sum_manhattan(vector<vector<int>>& state){
    int edge_len = state.size(), res = 0;
    for(int i = 0; i < edge_len; i++){
        for(int j = 0; j < edge_len; j++){
            if(state[i][j] != 0)
                res += abs((state[i][j]-1)/edge_len - i) + abs((state[i][j]-1)%edge_len -j); 
        }
    }
    return res;
}

bool DLS(State& state, const int& limit, const int& depth){
    if(depth + state.heuristic > limit) return false;
    if(state.heuristic == 0) return true;
    vector<State> next_states = state.get_next_states();
    for(State s : next_states){
        if(DLS(s, limit, depth+1)) return true;
    }
    return false;
}

int IDA(State& initial_state, const int& max_step){
    for(int l = 0; l <= max_step; l++){
        if(DLS(initial_state, l, 0))
            return l;
    }
    return -1;
}

int main(){
    int max_step = 45;
    int edge_len = 4;
    int x, zr, zc;
    vector<vector<int>> puzzle(edge_len, vector<int>(edge_len));
    for(int i = 0; i < edge_len; i++){
        for(int j = 0; j < edge_len; j++){
            scanf("%d", &x);
            if(x == 0){
                zr = i; zc = j;
            }
            puzzle[i][j] = x;
        }
    }
    State initial_state = State(puzzle, zc, zr, zc, zr, get_sum_manhattan(puzzle));
    printf("%d\n", IDA(initial_state, max_step));
}




Measured memory_bytes: 2876