#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<queue>
#define maxn 4
using namespace std;

struct Node
{
    int x,y,step,h;
    int data[maxn][maxn];
    friend bool operator < (Node a,Node b)
    {
        if(a.step+a.h==b.step+b.h)
            return a.h>b.h;
        return (a.step+a.h>b.step+b.h);
    }
    friend bool operator ==(Node a,Node b)
    {
        bool flag=true;
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++)
                if(a.data[i][j]!=b.data[i][j])
                    {
                        flag=false;
                        break;
                    }
        return flag;
    }
    int dis()
    {
        int i,j,sum;
        sum=0;
        for(i=0;i<maxn;i++)
            for(j=0;j<maxn;j++)
                if(data[i][j])
                {
                    int x=(data[i][j]-1)/maxn;
                    int y=(data[i][j]-1)%maxn;
                    sum+=abs(i-x)+abs(j-y);
                }
        return sum;
    }
    bool can_get()
    {
        int i,j,sum=0;
        for(i=0;i<16;i++)
            for(j=i+1;j<16;j++)
            {
                int x_=i/maxn;
                int y_=i%maxn;
                int xx=j/maxn;
                int yy=j%maxn;
                if(data[x_][y_]&&data[xx][yy]&&data[x_][y_]>data[xx][yy])
                    sum++;
            }
        sum+=x+1;
        if(sum%2==0)
            return true;
        return false;
    }
    string covert_string()
    {
        string st="";
        for(int i=0;i<maxn;i++)
            for(int j=0;j<maxn;j++)
                if(data[i][j]>9)
                    st+=(data[i][j]-10+'A');
                else
                    st+=(data[i][j]-0+'0');
        return st;
    }
};
priority_queue<Node> q;
map<string,int> mp;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};

void read(int &x){//读入正整数优化
	char ch = getchar();x = 0;
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int main()
{
    int i,j,k,x,cnt=0;
    Node p,p_,aim;
    for(i=0;i<maxn;i++)
        for(j=0;j<maxn;j++)
        {
            read(x);
            p.data[i][j]=x;
            if(x==0)
                p.x=i,p.y=j;
        }
    for(i=0;i<maxn;i++)
        for(j=0;j<maxn;j++)
            aim.data[i][j]=(i*maxn)+j+1;
    aim.data[3][3]=0;
    if(p==aim)
    {
        printf("0\n");
        return 0;
    }
    p.step=0;
    p.h=p.dis();
    q.push(p);
    mp[p.covert_string()]=1;
    while(!q.empty())
    {
        p=q.top();
        q.pop();
        for(i=0;i<4;i++)
        {
            int xx=p.x+dx[i];
            int yy=p.y+dy[i];
            if(xx>=0&&xx<maxn&&yy>=0&&yy<maxn)
            {
                for(j=0;j<maxn;j++)
                    for(k=0;k<maxn;k++)
                        p_.data[j][k]=p.data[j][k];
                swap(p_.data[xx][yy],p_.data[p.x][p.y]);
                p_.x=xx,p_.y=yy;
                p_.step=p.step+1;
                p_.h=p_.dis();
                if(p_==aim)
                {
                    printf("%d\n",p_.step);
                    return 0;
                }
                string st=p_.covert_string();
                if(mp.count(st)==0)
                {
                    q.push(p_);
                    mp[st]=1;
                }
            }
        }

    }
}



Measured memory_bytes: 92564