horsetraveldemoview.cpp

一个解决国际象棋的马周游问题的算法.本程序使用改善后的回溯算法来加速问题的解决.

// HorseTravelDemoView.cpp : implementation of the CHorseTravelDemoView class
//

#include "stdafx.h"
#include "HorseTravelDemo.h"

#include "HorseTravelDemoDoc.h"
#include "HorseTravelDemoView.h"

#include "SettingDlg.h"
#include "HorseTravel.h"

#include "MainFrm.h"

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

/////////////////////////////////////////////////////////////////////////////
// CHorseTravelDemoView

IMPLEMENT_DYNCREATE(CHorseTravelDemoView, CView)

BEGIN_MESSAGE_MAP(CHorseTravelDemoView, CView)
	//{{AFX_MSG_MAP(CHorseTravelDemoView)
	ON_COMMAND(ID_EXEC, OnExec)
	ON_COMMAND(ID_STOP, OnStop)
	ON_MESSAGE(UM_SHOWINFO, ShowWaitInfo)
	ON_MESSAGE(UM_HIDEINFO, HideWaitInfo)
	ON_COMMAND(ID_STOPDEMO, OnStopdemo)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHorseTravelDemoView construction/destruction

CHorseTravelDemoView::CHorseTravelDemoView()
{
	// TODO: add construction code here
	m_n = 8;
	m_d = 75;
	m_Path = NULL;
	m_curPos = 0;
	m_pDlgInfo = NULL;

	m_startX = 0;
	m_startY = 0;

	m_bStopDemo = FALSE;
}

CHorseTravelDemoView::~CHorseTravelDemoView()
{
	ReleaseSolvePath();
}

BOOL CHorseTravelDemoView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CHorseTravelDemoView drawing

void CHorseTravelDemoView::OnDraw(CDC* pDC)
{
	CHorseTravelDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	DrawChessBoard(pDC);//画棋盘
	ShowAllChesses(pDC);//画棋子
}

/////////////////////////////////////////////////////////////////////////////
// CHorseTravelDemoView diagnostics

#ifdef _DEBUG
void CHorseTravelDemoView::AssertValid() const
{
	CView::AssertValid();
}

void CHorseTravelDemoView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CHorseTravelDemoDoc* CHorseTravelDemoView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CHorseTravelDemoDoc)));
	return (CHorseTravelDemoDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CHorseTravelDemoView message handlers
//画棋盘
void CHorseTravelDemoView::DrawChessBoard(CDC* pDC)
{
	int i,j;
	for(i=0; i<m_n; i++)
	{
		for(j=0; j<m_n; j++)
		{
			if((i+j)%2 == 0)
			{
				//white
				CBrush WhiteBrush(RGB(255,255,255)),*pBrush;
				pBrush = pDC->SelectObject(&WhiteBrush);
				pDC->Rectangle(j*m_d,i*m_d,(j+1)*m_d,(i+1)*m_d);
				pDC->SelectObject(pBrush);
				WhiteBrush.DeleteObject();
			}
			else
			{
				//black
				CBrush BlackBrush(RGB(0,0,0)),*pBrush;
				pBrush = pDC->SelectObject(&BlackBrush);
				pDC->Rectangle(j*m_d,i*m_d,(j+1)*m_d,(i+1)*m_d);
				pDC->SelectObject(pBrush);
				BlackBrush.DeleteObject();
			}
		}
	}
}

//画棋子(马)
void CHorseTravelDemoView::DrawChess(CDC* pDC, int k)
{
	CString strNum;
	strNum.Format("%d",k+1);
	CPen pen(PS_SOLID,2,RGB(0,0,255)),*poldPen;
	CBrush brush(RGB(255,255,0)),*poldBrush;
	poldPen = pDC->SelectObject(&pen);
	poldBrush = pDC->SelectObject(&brush);

	int x = m_d*m_Path[k].col;
	int y = m_d*m_Path[k].row;
	int d = m_d/25;
	CRect rc(x+d,y+d,x+m_d-d,y+m_d-d);
	pDC->Ellipse(&rc);
	pDC->SetTextColor(RGB(255,0,0));
	pDC->SetBkMode(TRANSPARENT);
	pDC->DrawText(strNum,&rc,DT_SINGLELINE | DT_CENTER | DT_VCENTER);

	pDC->SelectObject(poldPen);
	pDC->SelectObject(poldBrush);
	pen.DeleteObject();
	brush.DeleteObject();
}

//显示正在求解信息
void CHorseTravelDemoView::ShowWaitInfo()
{
	m_pDlgInfo = new CDialog();
	m_pDlgInfo->Create(IDD_DIALOG_WAIT,AfxGetMainWnd());
	m_pDlgInfo->CenterWindow();
	m_pDlgInfo->ShowWindow(SW_SHOW);
	m_pDlgInfo->UpdateWindow();
}

//隐藏正在求解信息
void CHorseTravelDemoView::HideWaitInfo()
{
	if(m_pDlgInfo != NULL)
	{
		m_pDlgInfo->DestroyWindow();
		delete m_pDlgInfo;
		m_pDlgInfo = NULL;
	}
}

//算法执行和演示线程
UINT HorseTravelFunc(LPVOID pParam)
{
	CHorseTravelDemoView* pView = (CHorseTravelDemoView*)pParam;
	pView->SendMessage(UM_SHOWINFO);
	HorseTravel ht(pView->m_startY,pView->m_startX,pView->m_n);
	ht.HouseTravelIter();
	pView->SendMessage(UM_HIDEINFO);

	if(ht.IsHasSolve())
	{
		//Demo
		//pView->ReleaseSolvePath();
		pView->GetSolvePath(ht.GetSolvePath());
		pView->SetMenuState(2);
		pView->Demo();
	}
	else
	{
		pView->MessageBox("No solve!");
	}
	pView->SetMenuState(3);
	
	return 0;
}

//执行
void CHorseTravelDemoView::OnExec() 
{
	// TODO: Add your command handler code here
	CSettingDlg dlg;
	if(IDOK == dlg.DoModal())
	{
		m_n = dlg.m_ChessBoardSize;
		m_startX = dlg.m_StartX-1;
		m_startY = dlg.m_StartY-1;
		ResizeView();
		ReleaseSolvePath();
		Invalidate(false);
		UpdateWindow();

		SetMenuState(1);
		
		AfxBeginThread(HorseTravelFunc,(LPVOID)this,THREAD_PRIORITY_BELOW_NORMAL);
	}
}

//终止算法执行
void CHorseTravelDemoView::OnStop() 
{
	// TODO: Add your command handler code here
	AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_STOP,MF_GRAYED | MF_BYCOMMAND);
	HorseTravel::SetStop();
}

//演示过程
void CHorseTravelDemoView::Demo()
{
	int n = m_n*m_n;
	CClientDC dc(this);
	for(int i=0; i<n; i++)
	{
		if(m_bStopDemo)
		{
			m_curPos = n-1;
			m_bStopDemo = FALSE;
			Invalidate(FALSE);
			UpdateWindow();
			break;
		}
		Sleep(500);
		m_curPos = i;
		DrawChess(&dc,i);
	}
}

//获取求解数据
void CHorseTravelDemoView::GetSolvePath(Node* path)
{
	int n = m_n*m_n;	
	m_Path = new Pos[n];
	for(int i=0; i<n; i++)
	{
		m_Path[i].row = path[i].row;
		m_Path[i].col = path[i].col;
	}
}

//释放求解数据占用的堆空间
void CHorseTravelDemoView::ReleaseSolvePath()
{
	if(m_Path)
	{
		delete []m_Path;
		m_Path = NULL;
	}
}

//显示当前已显示的所有棋子
void CHorseTravelDemoView::ShowAllChesses(CDC* pDC)
{
	if(m_Path)
	{
		for(int i=0; i<=m_curPos; i++)
		{
			DrawChess(pDC,i);
		}
	}
}

//计算并重置视图的大小
void CHorseTravelDemoView::ResizeView()
{
	m_d = WIDTH/m_n;
	((CMainFrame*)AfxGetMainWnd())->ResizeWindow(m_d*m_n,m_d*m_n);
}

//终止过程演示
void CHorseTravelDemoView::OnStopdemo() 
{
	// TODO: Add your command handler code here
	m_bStopDemo = TRUE;
}

//设置菜单的使能状态
void CHorseTravelDemoView::SetMenuState(int state)
{
	switch(state)
	{
	case 1:
		AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_EXEC,MF_GRAYED | MF_BYCOMMAND);
		AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_STOP,MF_ENABLED | MF_BYCOMMAND);
		break;
	case 2:
		AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_STOP,MF_GRAYED | MF_BYCOMMAND);
		AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_STOPDEMO,MF_ENABLED | MF_BYCOMMAND);
		break;
	case 3:
		AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_STOPDEMO,MF_GRAYED | MF_BYCOMMAND);
	AfxGetMainWnd()->GetMenu()->GetSubMenu(2)->EnableMenuItem(ID_EXEC,MF_ENABLED | MF_BYCOMMAND);
		break;
	}
}