amazedoc.cpp

C++Example实用的算法:包括枚举

// AmazeDoc.cpp : implementation of the CAmazeDoc class
//

#include "stdafx.h"
#include "Amaze.h"

#include "AmazeDoc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc

IMPLEMENT_DYNCREATE(CAmazeDoc, CDocument)

BEGIN_MESSAGE_MAP(CAmazeDoc, CDocument)
//{{AFX_MSG_MAP(CAmazeDoc)
// NOTE - the ClassWizard will add and remove mapping macros here.
//    DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc construction/destruction

CAmazeDoc::CAmazeDoc()
{
	// TODO: add one-time construction code here
	m_pData = NULL;
	m_pDisData = NULL;
	m_nDisNum = 0;
	m_nWidth = 40;
	m_nHeight = 25;
}

CAmazeDoc::~CAmazeDoc()
{
	DeleteAmaze();
}

BOOL CAmazeDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;
	
	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)
	
	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc serialization

void CAmazeDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc diagnostics

#ifdef _DEBUG
void CAmazeDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CAmazeDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CAmazeDoc commands

void CAmazeDoc::CreateAmaze()
{
	int Ptr=0;
	int X, Y, Xn, Yn;
	int Dir, Dir2;
	int i, k;
	long Count0 = (2*m_nWidth+2) * (2*m_nHeight+2);
	
	DeleteAmaze();
	m_pData = new long[Count0];
	m_pDisData = new long[Count0];
	//初始化数组
	memset(m_pData, 0, sizeof(long) * Count0);
	//画上下边界
	for( i = 0 ; i <= 2 * m_nWidth; i++){
		AMAZEDATA(i, 0) = 1;
		AMAZEDATA(i, m_nHeight * 2) = 1;
	}
	
	//画左右边界
	for( i = 0 ; i <= 2 * m_nHeight; i++){
		AMAZEDATA(0, i) = 1;
		AMAZEDATA(m_nWidth * 2 , i) = 1;
	}
	
	Count0 = m_nWidth * m_nHeight;
	//画迷宫循环
	for( i = 0 ; i<= Count0; i++){
		Ptr = (Ptr + 997) % Count0;
		X = Ptr / m_nHeight;
		Y = Ptr - X * m_nHeight;
		if(!AMAZEDATA(2 * X, 2 * Y)){
			Dir = 4.0 * rand() / RAND_MAX + 1;
			Dir2 = Dir;
			do{
				Dir = Dir % 4 + 1;
				Xn = ((Dir == 1) - (Dir == 3)) + X;
				Yn = ((Dir == 2) - (Dir == 4)) + Y;
				if( AMAZEDATA(2 * Xn, 2 * Yn) )
					break;
				if( Dir == Dir2 ){
					X = Xn;
					Y = Yn;
				}
			}while(true);
			AMAZEDATA(2 * X , 2 * Y) = 1;
			AMAZEDATA(2 * Xn , 2 * Yn) = 1;
			AMAZEDATA(X + Xn , Y + Yn) = 1;
			Dir = 4.0 * rand() / RAND_MAX + 1;
			k = 0;
			do {
				k = k + 1;
				Dir = Dir % 4 + 1;
				Xn = ((Dir == 1) - (Dir == 3)) + X;
				Yn = ((Dir == 2) - (Dir == 4)) + Y;
				if(! AMAZEDATA(2 * Xn, 2 * Yn) ){
					//Call LineA(X, Y, Xn, Yn)
					AMAZEDATA(2 * X , 2 * Y) = 1;
					AMAZEDATA(2 * Xn , 2 * Yn) = 1;
					AMAZEDATA(X + Xn , Y + Yn) = 1;
					X = Xn;
					Y = Yn;
					Dir = 4.0 * rand() / RAND_MAX + 1;
					k = 0;
				}
			}while(k <= 4);
		}
	}
	
	//迷宫上边开口
	X = m_nWidth - 1;
	do {
		X = X + 1;
	}while( AMAZEDATA(X, 1) );
	AMAZEDATA(X, 0) = 0;
	
	//迷宫下边开口
	X = m_nWidth - 1;
	do {
		X = X + 1;
	}while( AMAZEDATA(X, 2 * m_nHeight - 1) );
	AMAZEDATA(X, 2 * m_nHeight) = 0;
	DisAmaze();
}

void CAmazeDoc::DisAmaze()
{
	int X, Y=1, Xn, Yn, k=0, n, n1, i;
	
	if(!m_pData)
		//无迷宫
		return;
	
	for( X = 0 ;X <= m_nWidth * 2; X++) {
		//寻找迷宫入口
		if(! AMAZEDATA(X, 0) )
			break;
	}
	
	*(m_pDisData) = X;
	*(m_pDisData+1) = 0;
	*(m_pDisData+2) = X;
	*(m_pDisData+3) = 1;
	m_nDisNum = 2;
	
	do{
		//由于迷宫一定有出口，
		//所以按固定方向搜索，必然会找到出口
		//当前Do循环即按一定方向遍历迷宫。
		for( n = 0 ; n<4; n++) { 
			n1 = (k + n) % 4;
			Xn = (n1 == 2) - (n1 == 0) + X;
			Yn = (n1 == 1) - (n1 == 3) + Y;
			if(! AMAZEDATA(Xn, Yn) ){
				
				for(i=0;i<m_nDisNum;i++) {
					if(*(m_pDisData + 2*i) == Xn && *(m_pDisData + 2*i+1) == Yn) break;
				}

				m_nDisNum = i;
				*(m_pDisData + 2*m_nDisNum) = Xn;
				*(m_pDisData + 2*m_nDisNum+1) = Yn;
				m_nDisNum++;
				X = Xn;
				Y = Yn;
				k = (n1 + 3) % 4;
				break;
			}
		}
		//当Y方向大于迷宫边界时，结束
		
	}while( Y != 2 * m_nHeight && Y > 0);
}