#include <cstdio>#include <cstring> #include <string> #include <map>#include <windows.h>#include <algorithm>using namespace std;struct Map{int data[4][4],x,y,tot,nxt;Map(){nxt = -1;tot = 0;}};map<string,bool>inqueue;string tmp;Map queue[4000000],temp[5];int t = 1,w = 2,right[4][4],ans = -1,Value[5];int px[5] = {0,-1,0,1,0},py[5] = {0,0,1,0,-1};int abs(int q){return q >= 0 ? q : 0 - q;}bool cmp(int aaa,int bbb){    aaa > bbb;//////////////////////////////////////////////////////////////////////////}int V(Map f){    int res = 0;    for(int i = 0;i < 4;i++)        for(int j = 0;j < 4;j++)            for(int k = 0;k < 4;k++)                for(int l = 0;l < 4;l++)                    if(f.data[i][j] == right[k][l])/////////////////////////////////////                        res += abs(i - k) + abs(j - l);    return res;}void print(int x){    if(queue[x].nxt != -1)        print(queue[x].nxt);    Sleep(1000);        system("cls");    for(int i = 0;i < 4;i++){        for(int j = 0;j < 4;j++)            printf("%3d",queue[x].data[i][j]);        printf("\n");    }    puts("");}void swap(int &A,int &B){int temp = A;A = B;B = temp;}bool judge(Map x){    for(int i = 0;i < 4;i++)        for(int j = 0;j < 4;j++)            if(x.data[i][j] != right[i][j])                return 0;    return 1;}void work(Map de){    int Qoos = 0;    for(int i = 0;i < 4;i++)        for(int j = 0;j < 4;j++)            tmp[++Qoos] = de.data[i][j];}bool Iq(Map x,bool pp){work(x);inqueue[tmp] = pp;}bool iq(Map x){work(x);return inqueue[tmp];}void bfs(){//    while(t < w){//        Map x;//        for(int i = 1;i <= 4;i++){//            x = queue[t];//            int xx = x.x + px[i],yy = x.y + py[i];//            if(xx < 0 || xx > 3 || yy < 0 || yy > 3)//            swap(x.data[x.x][x.y],x.data[xx][yy]);//            //            x.x = xx;x.y = yy;x.tot++;Iq(x,1);//            queue[w] = x;//            queue[w].nxt = t;///////////////////////////mmmmmmmmmmmmmaaaaaaaaaaaaaaaaaaaiiiiiiiiiiiinnn///            ///////////////////////////mmmmmmmmmmmmmaaaaaaaaaaaaaaaaaaaiiiiiiiiiiiinnn///            w++;//        }//        t++;//    }int tt = 0;    while(t < w){        Map x;        for(int i = 1;i <= 4;i++){//            printf("$");            temp[i] = queue[t];            int xx = temp[i].x + px[i];            int yy = temp[i].y + py[i];            if(xx < 0 || xx > 3 || yy < 0 || yy > 3){Value[i] = -1;continue;}            swap(temp[i].data[temp[i].x][temp[i].y],temp[i].data[xx][yy]);            if(iq(temp[i])){Value[i] = -1;continue;}            temp[i].x = xx;temp[i].y = yy;temp[i].tot++;Iq(temp[i],1);            Value[i] = V(temp[i]);        }        sort(Value + 1,Value + 4,cmp);        for(int i = 1;i <= 4;i++){//            printf("#");            if(Value[i] == -1)continue;            queue[w] = temp[i];            queue[w].nxt = t;            if(judge(queue[w])){ans = w;return;}            w++;        }        t++;    }}int main(){//    freopen("out.txt","w",stdout);    tmp = "                ";    for(int i = 0;i <= 3;i++)        for(int j = 0;j <= 3;j++){            scanf("%d",&queue[1].data[i][j]);            if(queue[1].data[i][j] == 0){queue[1].x = i;queue[1].y = j;}        }    int pos = 0;    for(int i = 0;i <= 3;i++)        for(int j = 0;j <= 3;j++)            right[i][j] = ++pos;    right[3][3] = 0;    if(judge(queue[1])){printf("right!\n");return 0;}    Iq(queue[1],1);puts("...");bfs();    puts("Done!");    if(ans == -1) printf("No Solution!\n");    else print(ans);    return 0;}/*0 4 82 6 31 7 50 4 82 6 31 7 50 4 82 6 31 7 50 2 31 8 47 6 51 2 34 5 67 8 01 2 34 5 67 0 81 2 3 45 6 7 89 0 11 1213 10 14 153 6 1 210 0 4 139 7 14 515 12 8 118 15 3 71 9 11 46 12 14 513 10 2 0*/