#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>

typedef struct child
{
    struct node * son;
    struct child * next;
}child_node;

typedef struct node
{
    struct node * father;
    int step;
    int checked;
    char map_string[17];
    struct node * next;
}map_node;

int Map[4][4];
map_node * Map_Que=NULL;
child_node * Final=NULL;
int MinStep=-1;
clock_t start,end;

void print_map(void)
{
    int i,xpos,ypos;
    for (i=0;i<16;i++)
    {
        xpos=i%4;
        ypos=i/4;
        if (Map[xpos][ypos]<10)
        {
            printf("%2u",Map[xpos][ypos]);
        }
        else
        {
            printf("%2c",Map[xpos][ypos]+55);
        }
        if (xpos==3) printf(" ");
    }
}

void string_to_map(char *map_string)
{
    int i,xpos,ypos;
    for(i=0;i<16;i++)
    {
        xpos=i%4;
        ypos=i/4;
        if (map_string[i]<='9')
        {
            Map[xpos][ypos]=map_string[i]-0x30;
        }
        else
        {
            Map[xpos][ypos]=map_string[i]-0x37;
        }
    }
}

char *map_to_string()
{
    static char map_string[17];
    int i,xpos,ypos;
    map_string[16]=0;
    for(i=0;i<16;i++)
    {
        xpos=i%4;
        ypos=i/4;
        if (Map[xpos][ypos]<10)
        {
            map_string[i]=Map[xpos][ypos]+0x30;
        }
        else
        {
            map_string[i]=Map[xpos][ypos]+0x37;
        }
    }
    return map_string;
}

int calculate_map_string(char*map_string,int mode)
{
    int i,xpos,ypos,x,y,distance,val,dist,times=14;
    distance=dist=0;
    //成功与否在你真正实现之前，我们能做的只能是评估。

    //而评估的方法千差万别，但对你修正自己的目标却是至关重要！

    for(i=0;i<16;i++)
    {
        if (map_string[i]==0x30) continue;
        xpos=i%4;
        ypos=i/4;
        val=map_string[i]-0x30;
        if (val>9) val-=7;
        if (val==i+1) times--;
        x=(val-1)%4;
        y=(val-1)/4;
        distance+=abs(x-xpos)+abs(y-ypos);
        dist+=(x-xpos)*(x-xpos)+(y-ypos)*(y-ypos);
    }
    //而且在不同的场合我们所需要的评估手段也不尽相同

    if (mode==1) return distance;
    return dist*times;
}

map_node *new_map_status(map_node * father_node,char *map_string,int steps)
{
    map_node *new_node;
    new_node=(map_node *)malloc(sizeof(map_node));
    if (new_node!=NULL)
    {
        //每一步的都是崭新的，但是也已经蕴藏了是否能成功的关键

        new_node->father=father_node;
        strcpy(new_node->map_string,map_string);
        new_node->step=steps;
        new_node->next=NULL;
        new_node->checked=0;
    }
    return new_node;
}

int compare_map(char *map1,int step1,char *map2,int step2)
{
    int dist1,dist2;
    dist1=calculate_map_string(map1,0);
    dist2=calculate_map_string(map2,0);
    if (dist1>dist2) return 1;
    if (dist1<dist2) return -1;
    //在成功之前，我们面对的竞争是残酷的，即使一点微小的差别，也会导致落选！

    if (step1>step2) return 1;
    if (step1<step2) return -1;
    return 0;
}

map_node * insert_map_que(map_node *father_node,char *map_string,int steps)
{
    map_node * queue=Map_Que;
    map_node * result=NULL;
    map_node * last=NULL;
    int checked=0;
    while (queue!=NULL)
    {
        //迟到会让机会永远跟你说再见

        if (checked==0 && queue->step<steps && strcmp(queue->map_string,map_string)==0) return NULL;
        //如果有人成功过，那么你所面临的淘汰可能是空前的！

        if (checked==1 && MinStep>0 && queue->step+calculate_map_string(queue->map_string,1)>MinStep)
        {
            if (last!=NULL)
            {
                last->next=queue->next;
                free(queue);
                queue=last->next;
                continue;
            }
            else
            {
                Map_Que=queue->next;
                free(queue);
                queue=Map_Que;
                continue;
            }
        }
        //先下手未必强，后来者也可居上！

        if (checked==1 && queue->step>steps && strcmp(queue->map_string,map_string)==0)
        {
                last->next=queue->next;
                free(queue);
                queue=last->next;
                continue;
        }
        //竞争的残酷，居然可以蔓延到下一代！

        if (checked==1 && queue->father!=NULL && queue->father->map_string!=NULL && strcmp(queue->father->map_string,map_string)==0)
        {
            queue->father=result;
            last=queue;
            queue=queue->next;
            continue;
        }
        //肃清运动一定会是彻底而残酷的！

        if (checked==1)
        {
            last=queue;
            queue=queue->next;
            continue;
        }
        //在队列中找到了自己的位置，那只是一切的开始！

        if (compare_map(map_string,steps,queue->map_string,queue->step)==-1 || queue->next==NULL)
        {
            result=new_map_status(father_node,map_string,steps);
            if (result==NULL)
            {
                printf("ERROR IN INSERT_MAP_QUE! ");
                exit(1) ;
            }
            if (last!=NULL)
            {
                last->next=result;
            }
            else
            {
                Map_Que=result;
            }
            result->next=queue;
            result->checked=0;
            checked=1;
        }
        last=queue;
        queue=queue->next;
    }
    return result;
}

void add_child(map_node* now_node)
{
    child_node * new_node;
    new_node=(child_node *)malloc(sizeof(child_node));
    if (new_node==NULL)
    {
        printf("ERROR IN APPLY MEMORY IN ADD_CHILD! ");
        exit(1) ;
    }
    new_node->son=now_node;
    new_node->next=Final;
    Final=new_node;
    return;
}

int develop_node(map_node* now_node)
{
    int i;
    char map_string[17];
    map_node* candidate;

    for (i=0;i<16;i++)
    {
        if (now_node->map_string[i]=='0')
        {
             //寻找出路的过程是漫长而乏味的，上下以求索，是成功前必由之路

             //Up Side Move

            strcpy(map_string,now_node->map_string);
            if (i/4>=1)
            {
                map_string[i-4]=now_node->map_string[i];
                map_string[i]=now_node->map_string[i-4];
                if (MinStep==-1 || calculate_map_string(map_string,1)+now_node->step<MinStep)
                {
                    //能够成为候选者应该是一种荣幸，特别是在有人成功以后！

                    candidate=insert_map_que(now_node,map_string,now_node->step+1);
                }
            }
            
            //Left Side Move

            strcpy(map_string,now_node->map_string);
            if (i%4>0)
            {
                map_string[i-1]=now_node->map_string[i];
                map_string[i]=now_node->map_string[i-1];
                if (MinStep==-1 || calculate_map_string(map_string,1)+now_node->step<MinStep)
                {
                    candidate=insert_map_que(now_node,map_string,now_node->step+1);
                }
            }

            //Right Side Move

            strcpy(map_string,now_node->map_string);
            if (i%4<3)
            {
                map_string[i+1]=now_node->map_string[i];
                map_string[i]=now_node->map_string[i+1];
                if (MinStep==-1 || calculate_map_string(map_string,1)+now_node->step<MinStep)
                {
                    candidate=insert_map_que(now_node,map_string,now_node->step+1);
                }
            }

            //Down Side Move

            strcpy(map_string,now_node->map_string);
            if (i/4<3)
            {
                map_string[i+4]=now_node->map_string[i];
                map_string[i]=now_node->map_string[i+4];
                if (MinStep==-1 || calculate_map_string(map_string,1)+now_node->step<MinStep)
                {
                    candidate=insert_map_que(now_node,map_string,now_node->step+1);
                }
            }

        }
    }
    return 0;
}

map_node *get_next_node()
{
    map_node* queue=Map_Que;
    map_node* last=NULL;
    while(queue!=NULL)
    {
        //成功者是暂时的强者，但它可以用来鉴定后来者的质素！

        if (MinStep>0 && queue->step+calculate_map_string(queue->map_string,1)>MinStep)
        {
            if (last!=NULL)
            {
                last->next=queue->next;
                free(queue);
                queue=last->next;
                continue;
            }
            else
            {
                Map_Que=queue->next;
                free(queue);
                queue=Map_Que;
                continue;
            }
        }
        //尚未触及的世界总是值得我们去探知的！

        if (queue->checked==0)
        {
            queue->checked=1;
            return queue;
        }
        last=queue;
        queue=queue->next;
    }
    return NULL;
}

int main()
{
    int i,now_distance=-1;
    int xpos,ypos;
    map_node* now_node;
    void *last;

    //机遇和挑战常常是以时间作为自变量的随机函数！

    //会有雷同，但不停变化！

    srand(time(NULL));
    for(i=0;i<16;i++)
    {
        xpos=i%4;
        ypos=i/4;
        Map[xpos][ypos]=0;
    }
    for(i=0;i<14;i++)
    {
        do
        {
            xpos=rand()*4/(RAND_MAX+1);
            ypos=rand()*4/(RAND_MAX+1);
        }while (Map[xpos][ypos]!=0);
        //面临的一切总不相同！

        Map[xpos][ypos]=i+1;
    }
    print_map();
    getchar();
    start=clock();
    //一切问题的开始总是那么简单，然而处理的过程有时却恰恰相反！

    Map_Que=new_map_status(NULL,map_to_string(),0);
    now_node=get_next_node();
    while(now_node!=NULL)
    {
        //探索的过程总是很乏味的，发现，判断，继续发现，继续判断，直到我们找到我们人为最好的解决方法

        develop_node(now_node);
        if (now_distance==-1 || calculate_map_string(now_node->map_string,0)<now_distance)
        {
            string_to_map(now_node->map_string);
            print_map();
            end=clock();
            printf("[%7lf] Step:%3u Distance:%2u ",(double)(end-start)/(double)CLOCKS_PER_SEC,now_node->step,calculate_map_string(now_node->map_string,0));
            now_distance=calculate_map_string(now_node->map_string,0);
        }

        if (calculate_map_string(now_node->map_string,0)==0)
        {
            if (MinStep==-1 || now_node->step<MinStep)
            {
                MinStep=now_node->step;
                end=clock();
                printf("[%7lf] Now Min Step Is %u ",(double)(end-start)/(double)CLOCKS_PER_SEC,MinStep);
            }

        }
        now_node=get_next_node();
    }
    printf(" ");
    end=clock();
    printf("[%7lf] Seeking Finished! ",(double)(end-start)/(double)CLOCKS_PER_SEC);
    printf(" ");
    if (MinStep!=-1)
    {
        now_node=Map_Que;
        while(now_node!=NULL)
        {
            //这些才是最终胜出的！

            if (calculate_map_string(now_node->map_string,0)==0)
            {
                add_child(now_node);
                while(Final!=NULL)
                {
                    string_to_map(Final->son->map_string);
                    print_map();
                    printf("Step %u Distance %u ",Final->son->step,calculate_map_string(Final->son->map_string,0));
                    last=Final;
                    Final=Final->next;
                    free(last);
                }
                printf("=============================== ");
            }
            now_node=now_node->next;
        }
    }
    //学会清理是很重要的！

    while(Map_Que!=NULL)
    {
        last=Map_Que->next;
        free(Map_Que);
        Map_Que=last;
    }
    exit(0);
}