cninegrid.cpp

利用Visual c++编程思想方法实现九宫问题(八数码)求解过程动态演示的程序

#include "stdafx.h"
#include "CNineGrid.h"
#include <process.h>


CNineGrid::CNineGrid()
{
	m_pEdit = NULL;
	m_pPathList = NULL;
	m_pPlaceList = NULL;
	m_pScanbuf = NULL;
	m_iPathsize = 0;
	m_iTime = 0;
	m_bAutoRun = false;
	m_bCannDynamic = true;
	Reset();
}

CNineGrid::~CNineGrid()
{
	if (m_pPathList != NULL)
	{
		delete[] m_pPathList;//delete运算符用来释放空间
	}

	if (m_pScanbuf != NULL)
	{
		delete[] m_pScanbuf;//delete运算符用来释放空间
	}
}

inline void CNineGrid::ArrayToDword(unsigned char *array , DWORD& data)
{
	Dynamic( 460 , 389 , 30);
	unsigned char night = 0;
	for ( int i = 0 ; i < 9 ; i ++)
	{
		if (array[i] == 8)
		{
			night = (unsigned char)i;
			break;
		}
	}
	
	array[night] = 0;
	data = 0;
	data =	 (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 | 
					 (DWORD)array[2] << 23 | (DWORD)array[3] << 20 | 
					 (DWORD)array[4] << 17 | (DWORD)array[5] << 14 | 
					 (DWORD)array[6] << 11 | (DWORD)array[7] <<  8 | 
					 (DWORD)array[8] <<  5 | night);
	
	array[night] = 8;
}

inline void CNineGrid::DwordToArray(DWORD data , unsigned char *array)//解压数据
{
	Dynamic( 1014 , 944 , 53);
	unsigned char chtem;
	for ( int i = 0 ; i < 9 ; i ++)
	{
		chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
		array[i] = chtem;
	}
	chtem = (unsigned char)(data & 0x0000001F);
	array[chtem] = 8;
}

bool CNineGrid::ComputeFeel()//计算路径
{
	Dynamic( 1274 , 1245 , 65);
	unsigned char *array = m_iChess;
	UINT i;
	const int MAXSIZE = 362880;
	unsigned char temparray[9];
	
	DWORD target , fountain , parent , parentID = 0 , child = 1;
	ArrayToDword(m_iTargetChess , target);
	ArrayToDword(array , fountain);

	if (fountain == target)
	{
		return false;
	}

	if (m_pScanbuf != NULL)
	{
		delete[] m_pScanbuf;
	}
	m_pScanbuf = new Scanbuf[MAXSIZE];
	AddTree(fountain ,m_pPlaceList);
	m_pScanbuf[ 0 ].Place = fountain;
	m_pScanbuf[ 0 ].ScanID = -1;

	clock_t tim = clock();

	while(parentID < MAXSIZE && child < MAXSIZE)
	{
		m_bCannDynamic = FALSE;
		parent = m_pScanbuf[parentID].Place;
		for ( i = 0 ; i < 4 ; i ++)
		{
			DwordToArray(parent , temparray);
			if (MoveChess(temparray,i))
			{
				ArrayToDword(temparray , fountain);
				if (AddTree(fountain, m_pPlaceList))
				{
					m_pScanbuf[ child ].Place = fountain;
					m_pScanbuf[ child ].ScanID = parentID;
					if (fountain == target)
					{
						m_bCannDynamic = TRUE;
						m_iTime = clock() - tim;
						GetPath(child);
						FreeTree(m_pPlaceList);
						delete[] m_pScanbuf;
						m_pScanbuf = NULL;
						return true;
					}
					child ++;
				}
			}
		} // for i
		parentID++;
	}

	m_iTime = clock() - tim;

	FreeTree(m_pPlaceList);
	delete[] m_pScanbuf;
	m_pScanbuf = NULL;
	return false;
}

inline bool CNineGrid::AddTree(DWORD place , PlaceList*& parent)//插入二叉树
{
	Dynamic( 2642 , 2578 , 129);
	if (parent == NULL)
	{
		parent = new PlaceList();
		parent->Left = parent->Right = NULL;
		parent->Place = place;
		return true;
	}
	if (parent->Place == place)
	{
		return false;
	}
	if (parent->Place > place)
	{
		return AddTree(place , parent->Right);
	}
	return AddTree(place , parent->Left);
}

void CNineGrid::FreeTree(PlaceList*& parent)
{
	//Dynamic( 2967 , 3011 , 149);
	if (parent != NULL)
	{
		if ( parent->Left != NULL)
			FreeTree(parent->Left);
		if ( parent->Right != NULL)
			FreeTree(parent->Right);
		delete parent;
		parent = NULL;
	}
}

inline bool CNineGrid::MoveChess(unsigned char *array , int way)//移动到空格的位置
{
	Dynamic( 3269 , 3205 , 162);
	int zero , chang;
	bool moveok = false;
	for ( zero = 0 ; zero < 9 ; zero ++)
	{
		if (array[zero] == 0)
			break;
	}
	POINT pnt;
	pnt.x = zero % 3;
	pnt.y = int(zero / 3);
	switch(way)
	{
	case 0 : //向上移
		if (pnt.y + 1 < 3)
		{
			chang = (pnt.y + 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 1 : //向下移
		if (pnt.y - 1 > -1)
		{
			chang = (pnt.y - 1) * 3 + pnt.x ;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 2 : //向左移
		if (pnt.x + 1 < 3)
		{
			chang = pnt.y * 3 + pnt.x + 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	case 3 : //向右移
		if (pnt.x - 1 > -1)
		{
			chang = pnt.y * 3 + pnt.x - 1;
			array[zero] = array[chang];
			array[chang] = 0;
			moveok = true;
		}
		break;
	}
	if (moveok && !m_bAutoRun)
	{
		m_iStepCount ++ ;
		
		DWORD temp1 ,temp2;
		ArrayToDword(array , temp1);
		ArrayToDword(m_iTargetChess , temp2);
	}
	return moveok;
}

bool CNineGrid::EstimateUncoil(unsigned char *array)//判断结果是奇数排列还是偶数排列
{
	Dynamic( 4488 , 4436 , 228);
	int sun = 0;
	for ( int i = 0 ; i < 8 ; i ++)
	{
		for ( int j = 0 ; j < 9 ; j ++)
		{
			if (array[j] != 0)
			{
				if (array[j] == i +1 )
					break;
				if (array[j] < i + 1)
					sun++;
			}
		}
	}
	if (sun % 2 == 0)
		return true;
	else
		return false;
}

void CNineGrid::GetPath(UINT depth)//获得最优路径
{
	Dynamic( 4811 , 4776 , 250);
	int now = 0 , maxpos = 100 ;
	UINT parentid;
	if (m_pPathList != NULL)
	{
		delete[] m_pPathList;//释放空间
	}
	m_pPathList = new PathList[maxpos];
	parentid = m_pScanbuf[depth].ScanID;
	
	DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);
	
	while(parentid != -1)
	{
		if (now == maxpos)
		{
			maxpos += 10;
			PathList * temlist = new PathList[maxpos];
			memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
			delete[] m_pPathList;
			m_pPathList = temlist;
		}
		DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
		parentid = m_pScanbuf[parentid].ScanID;
	}
	m_iPathsize = now;
}

unsigned __stdcall MoveChessThread(LPVOID pParam)

{
	CNineGrid * pGrid = (CNineGrid *)pParam;
	pGrid->Dynamic( 5515 , 5466 , 279);
	RECT rect;
	pGrid->m_iStepCount = 0;
	::GetClientRect(pGrid->m_hClientWin , &rect);
	pGrid->m_bCannDynamic = TRUE;
	
	pGrid->Dynamic( 5703 , 5655 ,  0);//for ( int i = pGrid->m_iPathsize ; i > 0 ; i --)
	for ( int i = pGrid->m_iPathsize ; i > 0 ; i --)
	{
		pGrid->Dynamic( 5768 , 5711 , 0);//memcpy(pGrid->m_iChess , pGrid->m_pPathList[i].Path , 9);
		memcpy(pGrid->m_iChess , pGrid->m_pPathList[i].Path , 9);
		pGrid->Dynamic( 5795 , 5772 , 0);//pGrid->m_iStepCount ++;
		pGrid->m_iStepCount ++;
		pGrid->Dynamic( 5854 , 5799 , 0);//::SendMessage(pGrid->m_hClientWin , WM_UPDATE , 0 , 0);
		::SendMessage(pGrid->m_hClientWin , WM_UPDATE , 0 , 0);
		pGrid->Dynamic( 5869 , 5858 , 0);//Sleep(1000);
		Sleep(500);
		pGrid->Dynamic( 5703 , 5655 , 0);//for ( int i = pGrid->m_iPathsize ; i > 0 ; i --)
	}

	pGrid->m_bAutoRun = false;
	return 0L;
}

void CNineGrid::ActiveShow(HWND hWin)
{
	Dynamic( 5961 , 5924 , 298);
	if (m_bAutoRun) return;
	m_bAutoRun = true;
	if (!ComputeFeel()) 
	{
		m_bAutoRun = true;
		return;
	}
	
	m_hClientWin = hWin;

	m_bCannDynamic = TRUE;

	HANDLE hThread;
	unsigned threadID;
	hThread = (HANDLE)_beginthreadex( NULL, 0, &MoveChessThread, this, 0, &threadID );
}

void CNineGrid::Reset()//随机打乱数组
{
	m_bCannDynamic = true;
	Dynamic( 6258 , 6235 , 315);
	if(m_bAutoRun) return;
	vector<int> vs;
	int i;
	for (i = 1 ; i < 9 ; i ++)
		vs.push_back(i);
	vs.push_back(0);
	random_shuffle(vs.begin(), vs.end()); //打乱顺序
	random_shuffle(vs.begin(), vs.end()); //打乱顺序
	for ( i = 0 ; i < 9 ; i ++)
	{
		m_iChess[i] = vs[i];//把打乱顺序后的元素赋值给九宫格
	}
	
	if (!EstimateUncoil(m_iChess))
	{
		unsigned char array[9] = {1,2,3,8,0,4,7,6,5};//重排的结果是奇数排列 
		memcpy(m_iTargetChess , array , 9);//把已经存在的array中的内容拷贝到m_iTargetChess中，(内存拷贝函数)
	}
	else
	{
		unsigned char array[9] = {1,2,3,4,5,6,7,8,0};//重排的结果是偶数排列
		memcpy(m_iTargetChess , array , 9);//把已经存在的array中的内容拷贝到m_iTargetChess中，(内存拷贝函数)
	}

	m_iStepCount = 0;
}

void CNineGrid::MoveChess(int way)//移动空格的位置
{
	MoveChess(m_iChess , way);
}

bool CNineGrid::OnButton(POINT pnt , HWND hWin)
{
	if (PtInRect(&m_rResetButton , pnt))
	{
		Reset();
		return true;
	}
	else if (PtInRect(&m_rAutoButton , pnt))
	{
		ActiveShow(hWin);
		return true;
	}
	return false;
}

void CNineGrid::Dynamic(int nStart , int nEnd , int nLine)
{
	if (!m_pEdit || !m_bCannDynamic )//判断显示代码显示框指针是否成功，并且可以动
	{
		return;//返回
	}
	Sleep(300);//延时函数,休眠300毫秒
	m_pEdit->SetFocus();//使代码显示框得到焦点
	if (nLine)//判断是否需要滚动到某行
	{
		m_pEdit->LineScroll(nLine);//滚动到某行
	}
	m_pEdit->SetSel(nStart , nEnd);//选中 从nStart 到 nEnd 中的字符
}