// pp.cpp : Defines the entry point for the application.
//

#include "stdafx.h"
#include "resource.h"
#include "stdio.h"
#include <time.h>
#include <fstream.h>

#define MAX_LOADSTRING 100
#define LEFT 150
#define TOP 20
#define RIGHT 450
#define BOTTOM 320
#define SIZE 100
#define	MOVE_UP 38
#define MOVE_DOWN 40
#define MOVE_LEFT 37
#define MOVE_RIGHT 39
#define STOP 0
#define USER 1
#define AUTO 2
#define DISPLAY 3
#define LEN 10
#define FAIL -1

// Global Variables:
HINSTANCE hInst;								// current instance
TCHAR szTitle[MAX_LOADSTRING];								// The title bar text
TCHAR szWindowClass[MAX_LOADSTRING];								// The title bar text
int map[10]={0};//存儲九宮圖數(shù)據(jù)
int *stack,*stack_top;//自定義堆棧
int *knowledge=NULL,*knowledge_top=NULL;//存儲知識，即已存儲的狀態(tài)即走法
int knowledge_len=0;//存儲已存記錄的長度（個數(shù)）
int sign;//標(biāo)志當(dāng)前游戲狀態(tài)（停止、玩家、自動、演示）
long len;//堆棧長度
long max_len;//堆棧最大長度
BOOL searching;//正在用Search進行搜索的標(biāo)志
HWND hwnd;//
BOOL study;//
FILE *fp;//外部文件
int playspeed=400;//演示速度
long step;//演示步數(shù)


// Foward declarations of functions included in this code module:
ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
LRESULT CALLBACK	About(HWND, UINT, WPARAM, LPARAM);
void ReDraw();//重畫九宮圖
void NewGame();//開始新游戲
void Auto();//開啟自動搜索
BOOL MoveUp();//向上移動
BOOL MoveLeft();//左
BOOL MoveRight();//右
BOOL MoveBottom();//下
int GetReverse();//獲取當(dāng)前狀態(tài)的逆序數(shù)
BOOL Success();//判斷是否成功
BOOL Search(int direct);//自動搜索的遞歸算法
BOOL Push();//將當(dāng)前狀態(tài)壓入自定義的堆棧
void Pop();//出棧，放入當(dāng)前狀態(tài)
void ShowWaiting();//顯示“Please Waiting”
void AutoSearch();//自動搜索的函數(shù)，被Auto調(diào)用，調(diào)用Search
void OpenStudy();//開啟學(xué)習(xí)狀態(tài)
void CloseStudy();//關(guān)閉學(xué)習(xí)狀態(tài)
void ReadKnowledge();//讀取已存狀態(tài)
void SaveKnowledge();//保存狀態(tài)
int SearchKnowledge();//在狀態(tài)中搜索當(dāng)前狀態(tài)，如有，返回應(yīng)走方向，否則返回0
void Study(int direct);//學(xué)習(xí)，保存當(dāng)前狀態(tài)及走法
int Judge();//在未搜索到的情況下判斷走法
void GetDistance(int pos1,int pos2,BOOL& narrow,int& direct);//獲得兩點位置關(guān)系



int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
 	// TODO: Place code here.
	MSG msg;
	HACCEL hAccelTable;

	// Initialize global strings
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_PP, szWindowClass, MAX_LOADSTRING);
	MyRegisterClass(hInstance);

	// Perform application initialization:
	if (!InitInstance (hInstance, nCmdShow)) 
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_PP);

	// Main message loop:
	while (GetMessage(&msg, NULL, 0, 0)) 
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg)) 
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}

	return msg.wParam;
}



//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
//  COMMENTS:
//
//    This function and its usage is only necessary if you want this code
//    to be compatible with Win32 systems prior to the 'RegisterClassEx'
//    function that was added to Windows 95. It is important to call this function
//    so that the application will get 'well formed' small icons associated
//    with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX); 

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= (WNDPROC)WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, (LPCTSTR)IDI_PP);
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= (LPCSTR)IDC_PP;
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);

	return RegisterClassEx(&wcex);
}

//
//   FUNCTION: InitInstance(HANDLE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // Store instance handle in our global variable

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }
	hwnd=hWnd;
   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  FUNCTION: WndProc(HWND, unsigned, WORD, LONG)
//
//  PURPOSE:  Processes messages for the main window.
//
//  WM_COMMAND	- process the application menu
//  WM_PAINT	- Paint the main window
//  WM_DESTROY	- post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
	TCHAR szHello[MAX_LOADSTRING];
	int the_Direct;
//	HMENU hmenu;
	LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);

	switch (message) 
	{
		case WM_CREATE:
			sign=STOP;
			stack=(int*)malloc(sizeof(int)*100000*LEN);
			stack_top=stack;
			len=0;
			max_len=100000;//初始化堆棧
			study=false;
			ReadKnowledge();//讀取已存知識
			break;
		case WM_COMMAND:
			wmId    = LOWORD(wParam); 
			wmEvent = HIWORD(wParam); 
			// Parse the menu selections:
			switch (wmId)
			{
				case IDM_NEW:
					NewGame();//開始新游戲
					break;
				case IDM_AUTO:
					Auto();//開啟自動搜索
					break;
				case IDM_STUDY:
					//hmenu=GetMenu(hWnd);
					if(study==false)
					{
					//	CheckMenuItem(hmenu,IDM_STUDY,MF_CHECKED);
						OpenStudy();
					//	study=true;
					}
					else
					{						
					//	CheckMenuItem(hmenu,IDM_STUDY,MF_UNCHECKED);
						CloseStudy();//打開、關(guān)閉學(xué)習(xí)開關(guān)
					//	study=false;
					}
					break;
				case IDM_LOWSPEED:
					playspeed=800;
					break;
				case IDM_MIDDLESPEED:
					playspeed=400;
					break;
				case IDM_HIGHSPEED:
					playspeed=100;
					break;
				case IDM_ABOUT:
				   DialogBox(hInst, (LPCTSTR)IDD_ABOUTBOX, hWnd, (DLGPROC)About);
				   break;
				case IDM_EXIT:
				   DestroyWindow(hWnd);
				   if(study==true)
					   CloseStudy();//存儲已存狀態(tài)
				   break;
				default:
				   return DefWindowProc(hWnd, message, wParam, lParam);
			}
			break;
		case WM_PAINT:
			hdc = BeginPaint(hWnd, &ps);
			 //TODO: Add any drawing code here...
			RECT rt;
			GetClientRect(hWnd, &rt);
			DrawText(hdc, szHello, strlen(szHello), &rt, DT_CENTER);
			EndPaint(hWnd, &ps);
			ReDraw();
			break;
		case WM_KEYDOWN:
			if(sign!=USER)
				return 0;
			the_Direct=int(wParam);
			switch(the_Direct)
			{
			case MOVE_UP:
				if(MoveUp()==false)
					MessageBeep(MB_OK);
				break;
			case MOVE_DOWN:
				if(MoveBottom()==false)
					MessageBeep(MB_OK);
				break;
			case MOVE_LEFT:
				if(MoveLeft()==false)
					MessageBeep(MB_OK);
				break;
			case MOVE_RIGHT:
				if(MoveRight()==false)//接收鍵盤輸入
					MessageBeep(MB_OK);
				break;
			default:
				return 0;
			}
			ReDraw();
			if(Success()==true)
			{
				if(MessageBox(hWnd,"再來一局?","勝利!!!",MB_OKCANCEL)==IDOK)
					NewGame();
				else
					sign=STOP;
			}
			break;
		case WM_DESTROY:
			PostQuitMessage(0);
			free(stack);
			SaveKnowledge();
			break;
		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
   }
   return 0;
}

// Mesage handler for about box.
LRESULT CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	switch (message)
	{
		case WM_INITDIALOG:
				return TRUE;

		case WM_COMMAND:
			if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL) 
			{
				EndDialog(hDlg, LOWORD(wParam));
				return TRUE;
			}
			break;
	}
    return FALSE;
}

void ReDraw()
{
	HDC hdc;
	hdc=GetDC(hwnd);
	HBRUSH hBr1,hBr2;
	LPPOINT lppoint=NULL;

	hBr1=(HBRUSH)GetStockObject(DKGRAY_BRUSH);
	SelectObject(hdc,hBr1);
	Rectangle(hdc,LEFT,TOP,RIGHT,BOTTOM);
	if(map[0]!=0)
	{
		hBr2=(HBRUSH)GetStockObject(GRAY_BRUSH);
		SelectObject(hdc,hBr2);
		int x,y;
		switch(map[0])
		{
		case 1:
			x=1;y=1;break;
		case 2:
			x=2;y=1;break;
		case 3:
			x=3;y=1;break;
		case 4:
			x=1;y=2;break;
		case 5:
			x=2;y=2;break;
		case 6:
			x=3;y=2;break;
		case 7:
			x=1;y=3;break;
		case 8:
			x=2;y=3;break;
		case 9:
			x=3;y=3;break;
		}
		Rectangle(hdc,LEFT+(x-1)*100,TOP+(y-1)*100,LEFT+x*100,TOP+y*100);
		//Draw the text
		for(int j=1;j<=9;j++)
		{
			switch(j)
			{
			case 1:
				x=1;y=1;break;
			case 2:
				x=2;y=1;break;
			case 3:
				x=3;y=1;break;
			case 4:
				x=1;y=2;break;
			case 5:
				x=2;y=2;break;
			case 6:
				x=3;y=2;break;
			case 7:
				x=1;y=3;break;
			case 8:
				x=2;y=3;break;
			case 9:
				x=3;y=3;break;
			}
			if(j!=map[0])
			{
				char out_text[2];
				sprintf(out_text,"%d",map[j]);
				TextOut(hdc,LEFT+(x-1)*100+45,TOP+(y-1)*100+45,out_text,1);
			}
		}
		DeleteObject(hBr2);
	}
	MoveToEx(hdc,LEFT+100,TOP,lppoint);
	LineTo(hdc,LEFT+100,BOTTOM);
	MoveToEx(hdc,LEFT+200,TOP,lppoint);
	LineTo(hdc,LEFT+200,BOTTOM);
	MoveToEx(hdc,LEFT,TOP+100,lppoint);
	LineTo(hdc,RIGHT,TOP+100);
	MoveToEx(hdc,LEFT,TOP+200,lppoint);
	LineTo(hdc,RIGHT,TOP+200);
	DeleteObject(hBr1);
	if(sign==DISPLAY)
	{
		char dstep[20];
		sprintf(dstep,"(Steps:%5ld     /",step);
		TextOut(hdc,230,345,dstep,18);
	}
	ReleaseDC(hwnd,hdc);
}

void NewGame()
{
	int i,j,k,temp;
	if(sign==USER)//判斷狀態(tài)
	{
		if(MessageBox(hwnd,"放棄當(dāng)前游戲?","提示",MB_OKCANCEL)==IDCANCEL)
		{
			return;
		}
		if(MessageBox(hwnd,"當(dāng)前游戲是否無解？","提示",MB_OKCANCEL)==IDOK)
			Study(FAIL);//如果此狀態(tài)無解，也存入狀態(tài)表中
	}
	srand((unsigned)time(NULL));
	map[0]=9;
	for(i=1;i<9;i++)
		map[i]=i;
	map[9]=0;
	do{
		for(i=0;i<10;i++)
		{
			j=rand()%9+1;
			k=rand()%9+1;
			temp=map[j];
			map[j]=map[k];
			map[k]=temp;
			if(map[j]==0)
				map[0]=j;
			if(map[k]==0)
				map[0]=k;
		}
	}while(GetReverse()==0);//隨機產(chǎn)生一個狀態(tài)
	ReDraw();
	sign=USER;
	stack_top=stack;
	len=0;
}
void Auto()
{
	if(sign!=USER)
		return;
	sign=AUTO;
	DWORD ID1;
	DWORD ID2;
	searching=true;
	CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)ShowWaiting,NULL,0,&ID1);
	//開啟搜索線程
	CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)AutoSearch,NULL,0,&ID2);
	//開啟顯示等待線程
	//主線程接受用戶輸入
}
BOOL MoveUp()
{
	if(map[0]==1||map[0]==2||map[0]==3)