seekview.cpp

此程序为数值算法分析里的跳马算法演示程序

// seekView.cpp : implementation of the CSeekView class
//

#include "stdafx.h"
#include "seek.h"

#include "seekDoc.h"
#include "seekView.h"

#include "input.h"       //user add
//#include "stack.h"

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

/////////////////////////////////////////////////////////////////////////////
// CSeekView

IMPLEMENT_DYNCREATE(CSeekView, CView)

BEGIN_MESSAGE_MAP(CSeekView, CView)
	//{{AFX_MSG_MAP(CSeekView)
	ON_COMMAND(ID_START_INPUT, OnStartInput)
	ON_COMMAND(ID_START_RUN, OnStartRun)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSeekView construction/destruction

CSeekView::CSeekView()
{
	// TODO: add construction code here
   pathNum=0;
   m_bAnimation=FALSE;
   m_interval=0;
   totalSteps=0;
   srand((unsigned)time(NULL));
   
}

CSeekView::~CSeekView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CSeekView drawing

void CSeekView::OnDraw(CDC* pDC)
{
	CSeekDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
    Print();
if(pathNum)
{for(int i=0;i<n*n;i++)
		PrintGrapth(pathRecord[i].x,pathRecord[i].y,0,i+1,false);
    PrintResult();
}
}

/////////////////////////////////////////////////////////////////////////////
// CSeekView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CSeekView message handlers

void CSeekView::OnStartInput() 
{
Input i;
if(i.DoModal()==IDOK)
{
	n=atoi(i.m_combo_n_val);
    x=atoi(i.m_combo_x_val);
	y=atoi(i.m_combo_y_val);
	m_bAnimation=i.m_check_val;
    m_interval=atoi(i.m_combo_s_val);
	pArray=new path[n*n];
	pathRecord=new path[n*n];
	int t,u;
 	for(t=0;t<n*n;t++)
	{
		pathRecord[t].x=pArray[t].x=-1;
		pathRecord[t].y=pArray[t].y=-1;
	}
	  for(t=0;t<10;t++)
		  for(u=0;u<10;u++)
			  flag[t][u]=0;
		  CMenu *pMenu=AfxGetMainWnd()->GetMenu();
		  ASSERT_VALID(pMenu);
		  pMenu->EnableMenuItem(ID_START_RUN,MF_ENABLED);
}//if	
}


void CSeekView::PrintResult()
{
int top=n*n;
char *px=new char[5];
char *py=new char[5];
CDC *pDC=GetDC();
int counter=0;
int spaceRow=10,spaceCol=10;
int startx=0,starty=(n+2)*40;
int cx=startx,cy=starty;
int numOfCol=0;
int space=10;
for(int i=0;i<top;i++)
{
	numOfCol++;
	if(numOfCol==10)
	{
		numOfCol=0;
		cx=startx;
	    cy += 20;
	}
	itoa(pathRecord[i].x,px,10);
	itoa(pathRecord[i].y,py,10);
	pDC->TextOut(cx,cy,"(");
	cx +=space;
	pDC->TextOut(cx,cy,px);
    cx +=space;
	pDC->TextOut(cx,cy,",");
    cx +=space;
	pDC->TextOut(cx,cy,py);
    cx +=space;
	pDC->TextOut(cx,cy,")");
    cx +=space;
}//for

}

void CSeekView::OnStartRun() 
{
pathNum=0;
totalSteps=0;
long start=0;
long end=0;
long elapse=0;
BeginWaitCursor();
ClearScreen();
Print();
start=clock();
int val=FindPath(x,y,0);
end=clock();
if(pathNum)
{
PrintResult();
bool delay;
if(m_bAnimation)
   delay=false;
else delay=true;
for(int i=0;i<n*n;i++)
       PrintGrapth(pathRecord[i].x,pathRecord[i].y,0,i+1,delay);	
}	
EndWaitCursor();
elapse=(end-start);
CString str=_T("");
str.Format("共执行了%ld步,耗时%ld毫秒,找到%d条可行路径!",totalSteps,elapse,pathNum);

if(!pathNum)
     MessageBox(str,"失败");
else MessageBox(str,"成功");
}

int CSeekView::FindPath(int x,int y,int step)
{
	totalSteps++;
	int i,j;
	flag[x][y]=1;
	pArray[step].x=x;
	pArray[step].y=y;
	if(pathNum==0 && m_bAnimation)
	{
		PrintGrapth(x,y,0,step+1,false);
	    Sleep(m_interval);
	}
	if(step>=n*n-1)
	{
		pathNum=1;
		for(int c=0;c<=step;c++)
		{			pathRecord[c].x=pArray[c].x;
					pathRecord[c].y=pArray[c].y;
				}//for
		return 1;
		
	}
	if((i=x+1)>=0 && (i=x+1)<n && (j=y+2)>=0 && (j=y+2)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x+2)>=0 && (i=x+2)<n && (j=y+1)>=0 && (j=y+1)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x+2)>=0 && (i=x+2)<n && (j=y-1)>=0 && (j=y-1)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x+1)>=0 && (i=x+1)<n && (j=y-2)>=0 && (j=y-2)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x-1)>=0 && (i=x-1)<n && (j=y+2)>=0 && (j=y+2)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x-2)>=0 && (i=x-2)<n && (j=y+1)>=0 && (j=y+1)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;
	
	if((i=x-2)>=0 && (i=x-2)<n && (j=y-1)>=0 && (j=y-1)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;

	if((i=x-1)>=0 && (i=x-1)<n && (j=y-2)>=0 && (j=y-2)<n && !flag[i][j])
		if(FindPath(i,j,step+1))
			return 1;
	
	flag[x][y]=0;

	pArray[step].x=pArray[step].y=-1;
    if(pathNum==0 && m_bAnimation)
	{
		PrintGrapth(x,y,1,step+1,false);
		Sleep(m_interval);
	}
	return 0;

}

void CSeekView::PrintGrapth(int x,int y,bool clean,int step,bool bDelay)
{
x =x*40+25;
y =y*40+25;
CClientDC dc(this);
//CPen *pen;
if(clean)
{
CPen pen(PS_SOLID,1,RGB(255,255,255));
dc.SelectObject(&pen);
dc.Ellipse(x,y,x+30,y+30);
dc.TextOut(x+7,y+7,"  ");
} //if    
else {
if(bDelay==true)
  Sleep(500);
CPen pen(PS_SOLID,1,RGB(0,0,255));
dc.SelectObject(&pen);
dc.Ellipse(x,y,x+30,y+30);
CString str;
str.Format("%d",step);
dc.TextOut(x+7,y+7,str);
}//else
}

void CSeekView::Print()
{
CDC *pDC=GetDC();
ASSERT_VALID(pDC);
int x,y;
int startx=20,starty=20;
int space=40;
CString str;
for(x=0;x<n;x++)
{
	str.Format("%d",x);
	pDC->TextOut(x*space+startx+10,starty-15,str);
	pDC->TextOut(startx-15,starty+x*space+10,str);
}

for(y=0;y<=n;y++)
{
 pDC->MoveTo(startx,y*space+starty);
 pDC->LineTo(startx+n*space,y*space+starty);
}
for(x=0;x<=n;x++)
{
pDC->MoveTo(x*space+startx,starty);
pDC->LineTo(x*space+startx,starty+n*space);
}
}

void CSeekView::ClearScreen()
{
CDC *pDC=GetDC();
	CRect clint;
	GetClientRect(&clint);
	pDC->SelectStockObject(NULL_PEN);
	pDC->SelectStockObject(WHITE_BRUSH);
	pDC->Rectangle(clint.left,clint.top,clint.right+10,clint.bottom);
    return;
}