#include <windows.h>
#include <time.h>
#include <math.h>

#define WINDOW_WIDTH  400
#define WINDOW_HEIGHT 420
#define MY_INTERVAL 500
#define NUMBER_OF_PIXEL 9

char* g_szApplicationName="旅行家问题（枚举法）";
char* g_szWindowClassName="LinrenWindowClass";

POINT mypix[NUMBER_OF_PIXEL];
POINT myline[NUMBER_OF_PIXEL+1]={0};
int showpos=0;

inline int RandInt(int x,int y){
    return rand()%(y-x+1)+x;
}

void travel(int *a,int *path,int len){
    int *p,*c,*tmp;
    int i,j,k,flg;
    int b=-1,d;

    p=(int*)malloc(sizeof(int)*len);
    c=(int*)malloc(sizeof(int)*len);
    tmp=(int*)malloc(sizeof(int)*len);
    memset(p,0,sizeof(int)*len);
    memset(c,0,sizeof(int)*len);

    k=0;flg=1;
    while(flg){
        for(p[k]=0;p[k]<len;p[k]++){
            for(i=0;i<k;i++){
                if(p[i]==p[k]) break;
            }
            if(i!=k) continue;
            c[k]++;
            if(k==len-1){
                d=0;
                for(i=0;i<len-1;i++) d+=*(a+p[i]*len+p[i+1]);
                d+=*(a+p[i]*len+p[0]);
                if(b==-1||d<b){
                    b=d;
                    memcpy(tmp,p,sizeof(int)*len);
                }
                for(i=len-1,j=1;c[i]==j&&i>=0;i--,j++);
                if(j==len+1){
                    flg=0;break;
                }
                k=i;
                if(k<len-1){
                    memset(c+k+1,0,sizeof(int)*(len-k-1));
                }
            }
            else k++;
        }
    }
    for(i=0;i<len;i++) path[i]=tmp[i];
    path[i]=tmp[0];
    free(p);free(c);free(tmp);
}

void myfun(LPVOID sc){
    HWND* hwnd=(HWND*)sc;
    int i,j,*list,ds;
    double dis;
    int path[NUMBER_OF_PIXEL+1]={0};
    char str[1024]={0};
    list=(int*)malloc(sizeof(int)*NUMBER_OF_PIXEL*NUMBER_OF_PIXEL);
    memset(list,0,sizeof(int)*NUMBER_OF_PIXEL*NUMBER_OF_PIXEL);
    for(i=0;i<NUMBER_OF_PIXEL;i++){
        for(j=i+1;j<NUMBER_OF_PIXEL;j++){
            dis=sqrt((mypix[i].x-mypix[j].x)*(mypix[i].x-mypix[j].x)+(mypix[i].y-mypix[j].y)*(mypix[i].y-mypix[j].y));
            ds=(int)(1000*dis);
            *(list+i*NUMBER_OF_PIXEL+j)=ds;
            *(list+j*NUMBER_OF_PIXEL+i)=ds;
        }
    }

    travel(list,path,NUMBER_OF_PIXEL);
    for(i=0;i<NUMBER_OF_PIXEL+1;i++){
        myline[i].x=mypix[path[i]].x;
        myline[i].y=mypix[path[i]].y;
    }
    free(list);
    while(1){
        Sleep(MY_INTERVAL);
        showpos++;
        if(showpos>NUMBER_OF_PIXEL+3) showpos=0;
    }
}

LRESULT CALLBACK WindowProc(HWND hwnd,UINT msg,WPARAM wParam,LPARAM lParam){
    static int cxClient,cyClient;
    static HDC hdcBackBuffer;
    static HBITMAP hBitmap;
    static HBITMAP hOldBitmap;

    switch(msg){
    case WM_CREATE:
        {
            RECT rect;
            GetClientRect(hwnd,&rect);
            cxClient=rect.right;
            cyClient=rect.bottom;
            int i,x,y;
            srand((int)time(0));
            for(i=0;i<100;i++) RandInt(0,0);
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                x=RandInt(20,380);y=RandInt(20,380);
                mypix[i].x=x;mypix[i].y=y;
                Ellipse(hdcBackBuffer,x-5,y-5,x+5,y+5);
            }
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                SetPixel(hdcBackBuffer,mypix[i].x,mypix[i].y,NULL);
            }
            hdcBackBuffer=CreateCompatibleDC(NULL);
            HDC hdc=GetDC(hwnd);
            hBitmap=CreateCompatibleBitmap(hdc,cxClient,cyClient);
            hOldBitmap=(HBITMAP)SelectObject(hdcBackBuffer,hBitmap);
            ReleaseDC(hwnd,hdc);
        }
        break;

    case WM_PAINT:
        {
            PAINTSTRUCT ps;
            BeginPaint(hwnd,&ps);
            BitBlt(hdcBackBuffer,0,0,cxClient,cyClient,NULL,NULL,NULL,WHITENESS);
            int i,x,y;
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                x=mypix[i].x;y=mypix[i].y;
                Ellipse(hdcBackBuffer,x-5,y-5,x+5,y+5);
            }
            for(i=0;i<NUMBER_OF_PIXEL&&i<showpos;i++){
                if(myline[i+1].x==0) break;
                MoveToEx(hdcBackBuffer,myline[i].x,myline[i].y,0);
                LineTo(hdcBackBuffer,myline[i+1].x,myline[i+1].y);
            }
            BitBlt(ps.hdc,0,0,cxClient,cyClient,hdcBackBuffer,0,0,SRCCOPY);
            EndPaint(hwnd,&ps);Sleep(10);
        }
        break;

    case WM_DESTROY:
        {
            SelectObject(hdcBackBuffer,hOldBitmap);
            DeleteDC(hdcBackBuffer);DeleteObject(hBitmap);
            PostQuitMessage(0);
        }break;
    }
    return DefWindowProc(hwnd,msg,wParam,lParam);
}

int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,
                   LPSTR szCmdLine,int iCmdShow){
    HWND hWnd;
    WNDCLASSEX winclass;
    winclass.cbSize        = sizeof(WNDCLASSEX);
    winclass.style         = CS_HREDRAW | CS_VREDRAW;
    winclass.lpfnWndProc   = WindowProc;
    winclass.cbClsExtra    = 0;
    winclass.cbWndExtra    = 0;
    winclass.hInstance     = hInstance;
    winclass.hIcon         = LoadIcon(NULL, IDI_APPLICATION);
    winclass.hCursor       = LoadCursor(NULL, IDC_ARROW);
    winclass.hbrBackground = NULL;
    winclass.lpszMenuName  = NULL;
    winclass.lpszClassName = g_szWindowClassName;
    winclass.hIconSm       = LoadIcon(NULL, IDI_APPLICATION);

    if (!RegisterClassEx(&winclass)){
        MessageBox(NULL,"RegisterClassEx Error!","error",0);return 0;
    }
    
    hWnd=CreateWindowEx(NULL,
        g_szWindowClassName,
        g_szApplicationName,
        WS_OVERLAPPED|WS_VISIBLE|WS_CAPTION|WS_SYSMENU,
        GetSystemMetrics(SM_CXSCREEN)/2-WINDOW_WIDTH/2,
        GetSystemMetrics(SM_CYSCREEN)/2-WINDOW_HEIGHT/2,
        WINDOW_WIDTH,
        WINDOW_HEIGHT,
        NULL,NULL,hInstance,NULL);

    if(!hWnd){
        MessageBox(NULL,"CreateWindowEx Error!","error",0);
    }

    ShowWindow(hWnd, iCmdShow);UpdateWindow(hWnd);
    
    HANDLE thrd;
    thrd=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)myfun,(LPVOID)&hWnd,0,NULL);

    MSG msg;
    bool bDone=false;
    while(!bDone){
        while(PeekMessage(&msg,NULL,0,0,PM_REMOVE)){
            if(msg.message==WM_QUIT){
                TerminateThread(thrd,NULL);
                bDone=true;
            }else{
                TranslateMessage(&msg);DispatchMessage(&msg);
            }
        }
        InvalidateRect(hWnd,NULL,TRUE);UpdateWindow(hWnd);
    }
    UnregisterClass(g_szWindowClassName,winclass.hInstance);
    return msg.wParam;
}