#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>

static const int N = 4;
static const int N2 = N * N;

static const int depth_limit = 45;

static std::array<int, 4> dx{0, -1, 0, 1};
static std::array<int, 4> dy{1, 0, -1, 0};
static std::array<char, 4> dchar{'u', 'l', 'd', 'r'};

struct Puzzle
{
    std::array<int, N2> state;
    int space;
    std::string path = "";

    // For map comparison
    bool operator<(const Puzzle &p) const
    {
        for (size_t i = 0; i < state.size(); ++i)
        {
            if (state[i] != p.state[i])
            {
                return state[i] < p.state[i];
            }
        }

        return false;
    }
};

struct State
{
    Puzzle p;
    int estimated;

    bool operator<(const State &s) const
    {
        return estimated > s.estimated;
    }
};

bool isTarget(Puzzle &p)
{
    for (int i = 0; i < p.state.size(); ++i)
    {
        if (p.state.at(i) != (i + 1))
            return false;
    }
    return true;
}

int MD(Puzzle p)
{
    int h = 0;
    for (int i = 0; i < p.state.size(); ++i)
    {
        if (i == p.space)
            continue;
        auto current_x = i % N;
        auto current_y = i / N;
        auto correct_x = (p.state[i] - 1) % N;
        auto correct_y = (p.state[i] - 1) / N;

        h += abs(current_x - correct_x);
        h += abs(current_y - correct_y);
    }

    return h;
}

auto print = [](std::array<int, N2>::iterator begin, std::array<int, N2>::iterator end) {
    auto itr = begin;
    while (itr != end)
    {
        std::cout << *itr << " ";
        itr++;
    }
    std::cout << std::endl;
};

std::string bfs(Puzzle &p)
{
    std::priority_queue<State> q;
    std::map<Puzzle, bool> visited;

    q.push(State{p, MD(p)});
    visited[p] = true;

    while (!q.empty())
    {
        auto u = q.top();
        q.pop();

        //   print(u.p.state.begin(), u.p.state.end());
        //  std::cout<<"Estimated = "<<u.estimated<<std::endl;

        if (isTarget(u.p))
        {
            return u.p.path;
        }

        int u_space_x = u.p.space % N;
        int u_space_y = u.p.space / N;

        for (size_t i = 0; i < dchar.size(); ++i)
        {
            auto nx = u_space_x + dx[i];
            auto ny = u_space_y + dy[i];

            if (0 <= nx && nx < N && 0 <= ny && ny < N)
            {
                auto v = u;
                auto next_space = ny * N + nx;

                std::swap(v.p.state[u.p.space], v.p.state[next_space]);
                v.p.space = next_space;
                v.p.path += dchar[i];
                v.estimated = v.p.path.length() + MD(v.p);

                if (!visited[v.p])
                {
                    //     printf("direction = %c, ET = %d, MD=%d\n", dchar[i], v.estimated, MD(v.p));
                    q.push(v);
                    visited[v.p] = true;
                    //   int tmp;
                    //  scanf("%d", &tmp);
                }
            }
        }
    }

    return "Unsolvable\n";
}

int main()
{
    Puzzle in;
    for (size_t i = 0; i < N2; ++i)
    {
        std::cin >> in.state[i];
        if (in.state[i] == 0)
        {
            in.state[i] = N2;
            in.space = i;
        }
    }

    auto ans = bfs(in);
    std::cout << ans.length() << std::endl;
}



Measured memory_bytes: 260620