#include <cstdlib>
#include <ctime>
#include<algorithm>
using namespace std;


extern "C"
{
    #include <windows.h>
    #include <tchar.h>
}


#define SIZE 18


LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam);
int FindParent(int*,int);
int SepToPoint(int,POINT*,POINT*);    //0代表左右关系  1代表上下关系
void BaseToRowCol(int,int*,int*);
void RowColToBase(int,int,int*);

HWND hwnd;
int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int nShowCmd)
{
    TCHAR szAppName[]=TEXT("first win");
    
    MSG msg;
    WNDCLASS wndclass;

    wndclass.style=CS_HREDRAW | CS_VREDRAW;
    wndclass.lpfnWndProc=WndProc;
    wndclass.cbClsExtra=0;
    wndclass.cbWndExtra=0;
    wndclass.hInstance=hInstance;
    wndclass.hIcon=LoadIcon(NULL,IDI_APPLICATION);
    wndclass.hCursor=LoadCursor(NULL,IDC_ARROW);
    wndclass.hbrBackground=(HBRUSH)GetStockObject(WHITE_BRUSH);
    wndclass.lpszMenuName=NULL;
    wndclass.lpszClassName=szAppName;

    if(!RegisterClass(&wndclass))
    {
        MessageBox(NULL,TEXT("error"),szAppName,MB_ICONERROR);
        return 0;
    }


    hwnd=CreateWindow(szAppName,
                      TEXT("hello"),
                      WS_OVERLAPPEDWINDOW^WS_MAXIMIZEBOX^WS_THICKFRAME,
                      20,    //CW_USEDEFAULT
                      50,
                      800,    //CW_USEDEFAULT,
                      600,    //CW_USEDEFAULT,
                      NULL,
                      NULL,
                      hInstance,
                      NULL);
    
    ShowWindow(hwnd,nShowCmd);
    UpdateWindow(hwnd);

    while(GetMessage(&msg,NULL,0,0))
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }


    return msg.wParam;
}

HDC hdc;
PAINTSTRUCT ps;

int collect[SIZE*SIZE];
int arrSep[SIZE*(SIZE-1)*2];
int sepIdx=0;

LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam)
{
    switch(message)
    {
        case WM_CREATE:
            srand(time(NULL));

            //初始化集合每个顶点
            for(int i=0;i<SIZE*SIZE;i++)
            {
                collect[i]=i;
            }
            //初始化边的数组
            for(int i=0;i<SIZE*(SIZE-1)*2;i++)
            {
                arrSep[i]=i;
            }
            //乱序边数组
            random_shuffle(arrSep,arrSep+SIZE*(SIZE-1)*2-1);

            //生成迷宫
            while(FindParent(collect,0)!=FindParent(collect,SIZE*SIZE-1))
            {
                int sep=arrSep[sepIdx++];
                POINT first,second;
                SepToPoint(sep,&first,&second);
                
                int firstBase,secondBase;
                RowColToBase(first.x,first.y,&firstBase);
                RowColToBase(second.x,second.y,&secondBase);
                
                int pFirst=FindParent(collect,firstBase);
                int pSecond=FindParent(collect,secondBase);
                //合并集合
                collect[pFirst]=pSecond;

            }
            break;
        case WM_PAINT:
            hdc=BeginPaint(hwnd,&ps);

            {    //画线
                int top=10,left=10;    //左上边距
                int sep=30;    //间隔
                //画上边
                MoveToEx(hdc,left,top,NULL);
                LineTo(hdc,left+SIZE*sep,top);
                //画下边
                MoveToEx(hdc,left,top+SIZE*sep,NULL);
                LineTo(hdc,left+SIZE*sep,top+SIZE*sep);
                //画左边
                MoveToEx(hdc,left,top,NULL);
                LineTo(hdc,left,top+SIZE*sep);
                //画右边
                MoveToEx(hdc,left+SIZE*sep,top,NULL);
                LineTo(hdc,left+SIZE*sep,top+SIZE*sep);

                //画剩余的障碍边
                POINT first,second;
                int dir;
                for(int i=sepIdx;i<SIZE*(SIZE-1)*2;i++)
                {
                    dir=SepToPoint(arrSep[i],&first,&second);
                    if(dir==0)    //first的右边
                    {
                        MoveToEx(hdc,left+(first.y+1)*sep,top+first.x*sep,NULL);
                        LineTo(hdc,left+(first.y+1)*sep,top+(first.x+1)*sep);
                    }
                    else    //first的下边
                    {
                        MoveToEx(hdc,left+first.y*sep,top+(first.x+1)*sep,NULL);
                        LineTo(hdc,left+(first.y+1)*sep,top+(first.x+1)*sep);
                    }
                }

            }


            EndPaint(hwnd,&ps);
            break;
        case WM_DESTROY:
            //MessageBox(NULL,TEXT("destroy"),TEXT("caption"),MB_YESNO);
            PostQuitMessage(0);
            return 0;

    }

    return DefWindowProc(hwnd,message,wParam,lParam);
}


int FindParent(int* collect,int v)
{
    int p=collect[v];
    while(p!=v)
    {
        v=p;
        p=collect[v];
    }
    return p;
}

int SepToPoint(int sep,POINT* first,POINT* second)    //边的坐标转换为相邻两块坐标
{
    int g=sep/(SIZE*2-1);
    int c=sep%(SIZE*2-1);
    int dir;
    if(c<SIZE-1)    //点是左右关系
    {
        first->x=g;
        first->y=c;

        second->x=first->x;
        second->y=first->y+1;

        dir=0;
    }
    else    //点是上下关系
    {
        first->x=g;
        first->y=c-(SIZE-1);

        second->x=first->x+1;
        second->y=first->y;

        dir=1;
    }
    return dir;
}

void BaseToRowCol(int base,int* row,int* col)
{
    *row=base/SIZE;
    *col=base%SIZE;
}

void RowColToBase(int row,int col,int* base)
{
    *base=row*SIZE+col;
}