horseview.cpp

马跳棋盘的回溯法程序

// HorseView.cpp : implementation of the CHorseView class
//

#include "stdafx.h"
#include "Horse.h"

#include "HorseDoc.h"
#include "HorseView.h"
#include "NewStartPosition.h"

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

/////////////////////////////////////////////////////////////////////////////
// CHorseView

IMPLEMENT_DYNCREATE(CHorseView, CView)

BEGIN_MESSAGE_MAP(CHorseView, CView)
	//{{AFX_MSG_MAP(CHorseView)
	ON_COMMAND(ID_MENU_END, OnMenuEnd)
	ON_COMMAND(ID_MENU_START, OnMenuStart)
	ON_COMMAND(ID_MENU_NEWSTARTPOS, OnMenuNewstartpos)
	ON_WM_LBUTTONDOWN()
	ON_WM_TIMER()
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHorseView construction/destruction

int Forward[8][2]={{-1,-2},{-1,2},{1,-2},{1,2},
{-2,-1},{-2,1},{2,-1},{2,1}};//定义数组，马的可能遍历方向
CHorseView::CHorseView()
{
	// TODO: add construction code here
	for(int i=0;i<8;i++)
       for(int j=0;j<8;j++)
          Qipan[i][j]=0; //棋盘初始化，0表示未遍历过，1表示遍历过
    count=0;
	width=43;
	nR=5;      //初始化棋子半径
	Step=0;
	m_x=1;
	m_y=1;
	for(i=0;i<64;i++)   //初始化栈空间为空，
	{
		i_x[i]=0;
		i_y[i]=0;
	}
}

CHorseView::~CHorseView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CHorseView drawing

void CHorseView::OnDraw(CDC* pDC)
{
	CHorseDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	//画棋盘
	//画横线    Y轴不变
	for(int i=1;i<=9;i++)
	{
		pDC->MoveTo(width,width*i);
		pDC->LineTo(width*9,width*i);
	}
	//画竖线       X轴不变
	for(int j=1;j<=9;j++)
	{
		pDC->MoveTo(width*j,width);
		pDC->LineTo(width*j,width*9);
	}
	pDC->MoveTo(0,width);
	pDC->LineTo(width*11,width);
	pDC->MoveTo(width,0);
	pDC->LineTo(width,width*11);
	CString S,T,T_x,T_y;
	//标出各轴
	S.Format("X轴");pDC->TextOut(width*11,width,S);
	S.Format("Y轴");pDC->TextOut(width,width*11,S);
	for(i=1;i<=8;i++)
		pDC->TextOut(width*i+20,width-20,48+i);
	for(i=1;i<=8;i++)
		pDC->TextOut(width-20,width*i+20,48+i);
	//画黑白格
	pDC->SelectStockObject(BLACK_BRUSH);
	for(i=1;i<=8;i+=2)
		for(j=1;j<=8;j+=2)
			pDC->Rectangle(width*j,width*i,width*(j+1),width*(i+1));
	for(i=2;i<=8;i+=2)
		for(j=2;j<=8;j+=2)
			pDC->Rectangle(width*j,width*i,width*(j+1),width*(i+1));
	//用绿色标记遍历过的格子
    for(i=0;i<Step;i++)
	{
	    if(Qipan[i_x[i]-1][i_y[i]-1]!=0)
		{
			CBrush brush;
	        brush.CreateSolidBrush(RGB(100,200,100));
            pDC->SelectObject(&brush);
		    pDC->Rectangle(width*i_x[i],width*i_y[i],
		                   width*(i_x[i]+1),width*(i_y[i]+1));
		}
	}
	//画棋子
	CBrush brush;
	brush.CreateSolidBrush(RGB(255,200,0));
    pDC->SelectObject(&brush);
	pDC->Ellipse(m_x*width+nR,m_y*width+nR,
		         (m_x+1)*width-nR,(m_y+1)*width-nR);
	//显示当前坐标和步数
	T_x.Format("当前X轴坐标: %d",m_x);
	pDC->TextOut(width*13,width*2,T_x);
	T_y.Format("当前Y轴坐标: %d",m_y);
	pDC->TextOut(width*13,width*3,T_y);
	T.Format("当前步数: %d",count);
	pDC->TextOut(width*13,width*5,T);
/*	CPen pen;
	pen.CreatePen(PS_SOLID,5,RGB(150,255,150));
	pDC->SelectObject( &pen );*/
	pDC->TextOut(m_x*width+12,m_y*width+12,"马");
}

/////////////////////////////////////////////////////////////////////////////
// CHorseView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CHorseView message handlers

//停止遍历菜单的函数
void CHorseView::OnMenuEnd() 
{
	KillTimer(1);
}

//开始遍历菜单的函数
void CHorseView::OnMenuStart() 
{
	count=0;
	for(int i=0;i<8;i++)
       for(int j=0;j<8;j++)
          Qipan[i][j]=0;
    for(i=0;i<64;i++)
	{
		i_x[i]=0;
		i_y[i]=0;
	}
	Step=0;
	Horse_Visit();
}

//重置开始位置的函数
void CHorseView::OnMenuNewstartpos() 
{
	KillTimer(1);
	count=0;
	for(int i=0;i<8;i++)
       for(int j=0;j<8;j++)
          Qipan[i][j]=0;
    for(i=0;i<64;i++)
	{
		i_x[i]=0;
		i_y[i]=0;
	}
	Step=0;

	CNewStartPosition dlgST;
	dlgST.m_nX=m_x;
	dlgST.m_nY=m_y;

	if(dlgST.DoModal()==IDOK)
	{
		m_x=dlgST.m_nX;
		m_y=dlgST.m_nY;
	}
	Invalidate();
}

void CHorseView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	
	CView::OnLButtonDown(nFlags, point);
}

void CHorseView::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	if(count>=64)
	{
		KillTimer(1);
		return;
	}
	Horse_Move(i_x[Step],i_y[Step]);
	Step++;
	CView::OnTimer(nIDEvent);
}

void CHorseView::Horse_Move(int a, int b)
{
    count++;
    m_x=a;
	m_y=b;
    Invalidate();
}

//马的遍历
void CHorseView::Horse_Visit()
{
    int i,j,start,step = 0,order;
    start = 0;    //从0号着法开始顺序检查
    do
    {
        for(i = 0;i < 8;i++)
            for(j = 0;j < 8;j++)
                Qipan[i][j] = 0;        //清棋盘
        for(i=0;i<64;i++)
        {
            i_x[i]=0;
            i_y[i]=0;
		}
        Qipan[m_x-1][m_y-1] = 1;
        i = m_x-1;
        j = m_y-1;
        i_x[step]=m_x;
	    i_y[step]=m_y;
        for(step = 2;step <= 64;step++)
        {
            order = Select_NextExit(i,j,start);
            if( order == -1)
                break;                   //没有出口
            i = i + Forward[order][0];   //前进一步
            j = j + Forward[order][1];
            Step++;
	        i_x[Step]=i+1;
            i_y[Step]=j+1;
            Qipan[i][j] = 1;    //标记遍历过的格子
        }
        if(step > 64)
           break;        //走出棋盘了,自然应该结束循环
        start ++;        //最先检查的着法序号增1
	}while(step <= 64);
	this->SetTimer(1,1000,NULL);    //设置定时器
	Step=0;
}

//选下一出口,start是顺序选择着法的开始序号
int CHorseView::Select_NextExit(int i, int j, int start)
{
    int   min_nexit,nexit,temp,a[8],b[8],k,result;
    nexit = Exit_Number(i,j,start,a);    //确定(i,j)的出口个数
    if(nexit == 0)
        return(-1);        //没有出口
    for(min_nexit = 9,k = 0;k < nexit;k++)   //逐一考察各个出口
    {
        temp = Exit_Number(i + Forward[a[k]][0],j + Forward[a[k]][1],start,b);
        if(temp < min_nexit)
        {
            min_nexit = temp;
            result = a[k];
        }
    }
    return result;
}

//求(i,j)的出口数,和各出口号于array[],start是顺序选择着法的开始序号
int CHorseView::Exit_Number(int i, int j, int start, int array[])
{
    int a,b,k,count;
    for(count = k = 0;k < 8;k++)
    {
        a = i + Forward[(start + k) % 8][0];
        b = j + Forward[(start + k) % 8][1];
        if((a >= 0 && a < 8) && (b >= 0 && b < 8) && Qipan[a][b] == 0)
            array[count ++ ] = (start + k) % 8;
    }
    return count;        //返回出口数
}