seekview_back.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;

}

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();

	for(int i=0;i<n*n;i++)
		PrintGrapth(pathRecord[i].x,pathRecord[i].y,0,i+1);
    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];
	check=new char[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;
}//if	
}

BOOLEAN CSeekView::IsAccess(int x, int y)
{
if(x<n && x>=0 && y <n && y>=0 && (check[y*n+x]=='n'))
    return TRUE;
else return FALSE;
}



BOOLEAN CSeekView::IsFinish(int steps)
{
if(steps != (n*n))
	return FALSE;
for (int i=0;i<n*n;i++)
	{
		if(check[i] =='n')
		     return FALSE;
	}//for
return TRUE;	
}

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;
BeginWaitCursor();
ClearScreen();
Print();
if(FindPath(x,y,0))
   pathNum=1;
EndWaitCursor();

CString str=_T("");
str.Format("找到%d条路径!",pathNum);

if(!pathNum)
     MessageBox("找不到可行的路径!","失败");
else MessageBox(str,"成功");
pathNum=0;	
}
 

void CSeekView::Find()
{
int top=0;
int steps=1;
pArray[top].x=x;
pArray[top].y=y;
check[x+y*n]='y';
int temx=x;
int temy=y;
BeginWaitCursor();
while(top >=0)
{
if(IsFinish(steps))
{
PrintResult();
pathNum=1;
return;
}//if
temx=pArray[top].x;
temy=pArray[top].y;
if(IsAccess(temx-1,temy-2) && pDirection[top][0] !='1')
{
	pDirection[top][0]='1';
	top++;
	pArray[top].x=temx-1;
	pArray[top].y=temy-2;
	check[(temx-1)+(temy-2)*n]='y';
	steps ++;
	continue;
}
else if(IsAccess(temx-2,temy-1) && pDirection[top][1] !='1')
{
	pDirection[top][1]='1';
	top++;
	pArray[top].x=temx-2;
	pArray[top].y=temy-1;
	check[temx-2+(temy-1)*n]='y';
	steps ++;
	continue;
}
else if(IsAccess(temx-2,temy+1) && pDirection[top][2] !='1')
{
	pDirection[top][2]='1';
	top++;
	pArray[top].x=temx-2;
	pArray[top].y=temy+1;
	check[temx-2+(temy+1)*n]='y';
	steps ++;
	continue;
}
else if(IsAccess(temx-1,temy+2) && pDirection[top][3] !='1')
{
	pDirection[top][3]='1';
	top++;
	pArray[top].x=temx-1;
	pArray[top].y=temy+2;
	check[temx-1+(temy+2)*n]='y';
	steps ++;
continue;
}
else if(IsAccess(temx+1,temy+2) && pDirection[top][4] !='1')
{
	pDirection[top][4]='1';
	top++;
	pArray[top].x=temx+1;
	pArray[top].y=temy+2;
	check[temx+1+(temy+2)*n]='y';
	steps ++;
continue;
}
else if(IsAccess(temx+2,temy+1) && pDirection[top][5] !='1')
{
	pDirection[top][5]='1';
	top++;
	pArray[top].x=temx+2;
	pArray[top].y=temy+1;
	check[temx+2+(temy+1)*n]='y';
	steps ++;
	continue;
}
else if(IsAccess(temx+2,temy-1) && pDirection[top][6] !='1')
{
	pDirection[top][6]='1';
	top++;
	pArray[top].x=temx+2;
	pArray[top].y=temy-1;
	check[temx+2+(temy-1)*n]='y';
	steps ++;
	continue;
}
else if(IsAccess(temx+1,temy-2) && pDirection[top][7] !='1')
{
	pDirection[top][7]='1';
	top++;
	pArray[top].x=temx+1;
	pArray[top].y=temy-2;
	check[temx+1+(temy-2)*n]='y';
	steps ++;
	continue;
}
 
	check[temx+temy*n]='n';
	top--;
	if(top <0)
	{MessageBox("under flow!");
	break ;
	}
    steps--;
}//while */

EndWaitCursor();

CString str=_T("");
str.Format("共找到%d条路径!",pathNum);

if(!pathNum)
     MessageBox("找不到可行的路径!","失败");
else MessageBox(str,"成功");
pathNum=0;

}

int CSeekView::FindPath(int x,int y,int step)
{
	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);
		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
		PrintResult();//打印完整的跳马路径
	    for(int i=0;i<n*n;i++)
		        PrintGrapth(pathRecord[i].x,pathRecord[i].y,0,i+1);	
		return 1;
		
	}
	//寻找下一步位置，共有八种可选位置，逐一迳行试探，
	//如果符合要求(此位置不越界，在棋盘内，且此点未被跳过),
	//则继续递归调用寻找此位置的下一位置，如此点不符合要求，
	//则返回0，递归回退。
	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;
	
	//对没找到合适位置的处理
	//至当前位置状态为0，恢复未跳过状态
	flag[x][y]=0;
	
	//清除设置记录跳过位置的坐标
	pArray[step].x=pArray[step].y=-1;
    if(pathNum==0 && m_bAnimation)
	{
		PrintGrapth(x,y,1,step);
		Sleep(m_interval);
	}
	return 0;

}

void CSeekView::PrintGrapth(int x,int y,bool clean,int step)
{
x =x*40+25;
y =y*40+25;
CDC *pDC=GetDC();
ASSERT_VALID(pDC);
CPen *pen;
if(clean)
{
pen=new CPen(PS_SOLID,1,RGB(255,255,255));
pDC->SelectObject(pen);
pDC->Ellipse(x,y,x+30,y+30);
pDC->TextOut(x+7,y+7,"  ");
} //if    
else {
pen=new CPen(PS_SOLID,1,RGB(0,0,255));
pDC->SelectObject(pen);
pDC->Ellipse(x,y,x+30,y+30);
CString str;
str.Format("%d",step);
pDC->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;
}