canvasframe.cpp

走迷宫程序

// canvasFrame.cpp : implementation file
//

#include "stdafx.h"
#include "canvasr.h"
#include "canvasFrame.h"

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

struct list             //定义链表结构
{
	int m;
	int n;
	struct list *next;  //指向下一个节点
	struct list *back;  //指向前一个节点
};
typedef struct list node;  //定义节点
typedef node *pointer;     //定义动态指针


/////////////////////////////////////////////////////////////////////////////
// canvasFrame

IMPLEMENT_DYNCREATE(canvasFrame, CFrameWnd)

int maze[8][8] = {1,1,/*2*/1,1,1,1,1,1,/*1*/2,0,0,1,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1,0,1,0,1,0,0,/*3*/1,1,/*1*/3,1,1,1,1,1,1};
BOOL pass[8][8];
int i,j,m,n,lastm,lastn;
BOOL start= true,search= true,go;
pointer ptr,preptr,first;
char str[10];

canvasFrame::canvasFrame()
{
	RECT rect;
	Create(NULL,"绘图窗口",WS_OVERLAPPEDWINDOW,CRect(0,0,330,380));
	CClientDC dc(this);
	int width = dc.GetDeviceCaps(HORZRES);
	int height = dc.GetDeviceCaps(VERTRES);
	GetWindowRect( &rect );
	width = ( width - ( rect.right - rect.left ))/2 ;
	height = (height - (rect.bottom - rect.top ))/2 ;
	MoveWindow( width , height , (rect.right - rect.left ) , (rect.bottom - rect.top ) ,true);
	mdc = new CDC;
	mdc->CreateCompatibleDC(&dc);
	tile = new CBitmap;
	ball = new CBitmap;
	tile->m_hObject = (HBITMAP)::LoadImage(NULL,"tile.bmp",IMAGE_BITMAP,40,40,LR_LOADFROMFILE);
	ball->m_hObject = (HBITMAP)::LoadImage(NULL,"ball.bmp",IMAGE_BITMAP,40,40,LR_LOADFROMFILE);
	for(i=0;i<7;i++)
	{
		for(j=0;j<7;j++)
			if(maze[i][j]==2)
				break;
		if(maze[i][j]==2)
			break;
	}
	m = i;
	n = j;
	ptr = (pointer)malloc(sizeof(node));
	ptr->m = m;
	ptr->n = n;
	ptr->next = NULL;
	ptr->back = NULL;
	first = ptr;
}

canvasFrame::~canvasFrame()
{
	delete tile;
	delete ball;
	delete mdc;
	ptr = first;
	while(ptr->next)
	{
		ptr = ptr->next;
		free(ptr->back);
	}
	free(ptr);
}


BEGIN_MESSAGE_MAP(canvasFrame, CFrameWnd)
	//{{AFX_MSG_MAP(canvasFrame)
	ON_WM_TIMER()
	ON_WM_CREATE()
	ON_WM_KEYDOWN()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// canvasFrame message handlers

void canvasFrame::OnTimer(UINT nIDEvent) 
{
	if(start)
		Start();       //开始搜寻
	else
	{
		if(search)
			Search();  //进行搜寻
		if(go)
			Go();      //显示最短路径

	}
	CFrameWnd::OnTimer(nIDEvent);
}

void canvasFrame::Start()
{
	CClientDC dc(this);
	mdc->SelectObject(tile);
	for(i=0;i<=7;i++)
		for(j=0;j<=7;j++)
			if(maze[i][j] == 1)
				dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY);
	mdc->SelectObject(ball);
	dc.BitBlt(ptr->n*40,ptr->m*40,40,40,mdc,0,0,SRCCOPY);
	start = false;
	lastn = ptr->n;
	lastm = ptr->m;
}

void canvasFrame::Go()
{
	CClientDC dc(this);
	m = ptr->m;
	n = ptr->n;
	mdc->SelectObject(tile);
	for(i=0;i<=7;i++)
		for(j=0;j<=7;j++)
			if(maze[i][j] == 1)
				dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY);
	mdc->SelectObject(ball);
	dc.BitBlt(n*40,m*40,40,40,mdc,0,0,SRCCOPY);
	if(maze[m][n] == 3)
	{
		dc.TextOut(120,320,"最短路径");
		go = false;
	}
	else
		ptr = ptr->next;
}

void canvasFrame::Search()
{
	CClientDC dc(this);
	mdc->SelectObject(tile);
	for(i=0;i<=7;i++)
		for(j=0;j<=7;j++)
			if(maze[i][j] == 1)
				dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY);
	mdc->SelectObject(ball);
	lastn = ptr->n;
	lastm = ptr->m;
	if(maze[m+1][n]==1)    //下一格是墙
		if(maze[m][n+1] == 1)     //右一格是墙
			if(maze[m][n-1] ==1)   //左一格是墙
				if(maze[m-1][n] == 1)   //上一格是墙
				{
					if(ptr->back != NULL)
					{
						ptr = ptr->back;
						free(ptr->next);
						ptr->next = NULL;
					}
					m = ptr->m;
					n = ptr->n;
				}
				else
					if(pass[m-1][n])    //上一格走过
					{
						if(ptr->back != NULL)
						{
							ptr = ptr->back;
							free(ptr->next);
							ptr->next = NULL;
						}
						m = ptr->m;
						n = ptr->n;
					}
					else
					{
						m-=1;    //往上一格
						ptr->next = (pointer)malloc(sizeof(node));
						ptr->next->m = m;
						ptr->next->n = n;
						preptr = ptr;
						ptr->next->next = NULL;
						pass[m][n] = true;
						ptr = ptr->next;
						ptr->back = preptr;
					}
			else
				if(pass[m][n-1])   //左一格走过
					if(maze[m-1][n] == 1)   //上一格是墙
					{
						if(ptr->back != NULL)
						{
							ptr = ptr->back;
							free(ptr->next);
							ptr->next = NULL;		
						}
						m = ptr->m;
						n = ptr->n;
					}
					else
						if(pass[m-1][n])    //上一格走过
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
						{
							m-=1;    //往上一格
							ptr->next = (pointer)malloc(sizeof(node));
							ptr->next->m = m;
							ptr->next->n = n;
							preptr = ptr;
							ptr->next->next = NULL;
							pass[m][n] = true;
							ptr = ptr->next;
							ptr->back = preptr;
						}
				else
				{
					n-=1;    //往左一格
					ptr->next = (pointer)malloc(sizeof(node));
					ptr->next->m = m;
					ptr->next->n = n;
					preptr = ptr;
					ptr->next->next = NULL;
					pass[m][n] = true;
					ptr = ptr->next;
					ptr->back = preptr;
				}
		else
			if(pass[m][n+1])      //右一格走过
				if(maze[m][n-1] ==1)   //左一格是墙
					if(maze[m-1][n] == 1)   //上一格是墙
					{
						if(ptr->back != NULL)
						{
							ptr = ptr->back;
							free(ptr->next);
							ptr->next = NULL;
						}
						m = ptr->m;
						n = ptr->n;
					}
					else
						if(pass[m-1][n])    //上一格走过
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
						{
							m-=1;    //往上一格
							ptr->next = (pointer)malloc(sizeof(node));
							ptr->next->m = m;
							ptr->next->n = n;
							preptr = ptr;
							ptr->next->next = NULL;
							pass[m][n] = true;
							ptr = ptr->next;
							ptr->back = preptr;
						}
				else
					if(pass[m][n-1])   //左一格走过
						if(maze[m-1][n] == 1)   //上一格是墙
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
							if(pass[m-1][n])    //上一格走过
							{
								if(ptr->back != NULL)
								{
									ptr = ptr->back;
									free(ptr->next);
									ptr->next = NULL;
								}
								m = ptr->m;
								n = ptr->n;
							}
							else
							{
								m-=1;    //往上一格
								ptr->next = (pointer)malloc(sizeof(node));
								ptr->next->m = m;
								ptr->next->n = n;
								preptr = ptr;
								ptr->next->next = NULL;
								pass[m][n] = true;
								ptr = ptr->next;
								ptr->back = preptr;
							}
					else
					{
						n-=1;    //往左一格
						ptr->next = (pointer)malloc(sizeof(node));
						ptr->next->m = m;
						ptr->next->n = n;
						preptr = ptr;
						ptr->next->next = NULL;
						pass[m][n] = true;
						ptr = ptr->next;
						ptr->back = preptr;
					}
			else
			{
				n+=1;    //往右一格
				ptr->next = (pointer)malloc(sizeof(node));
				ptr->next->m = m;
				ptr->next->n = n;
				preptr = ptr;
				ptr->next->next = NULL;
				pass[m][n] = true;
				ptr = ptr->next;
				ptr->back = preptr;
			}
	else
		if(pass[m+1][n])   //下一格走过
			if(maze[m][n+1] == 1)     //右一格是墙
				if(maze[m][n-1] ==1)   //左一格是墙
					if(maze[m-1][n] == 1)   //上一格是墙
					{
						if(ptr->back != NULL)
						{
							ptr = ptr->back;
							free(ptr->next);
							ptr->next = NULL;
						}
						m = ptr->m;
						n = ptr->n;
					}
					else
						if(pass[m-1][n])    //上一格走过
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
						{
							m-=1;    //往上一格
							ptr->next = (pointer)malloc(sizeof(node));
							ptr->next->m = m;
							ptr->next->n = n;
							preptr = ptr;
							ptr->next->next = NULL;
							pass[m][n] = true;
							ptr = ptr->next;
							ptr->back = preptr;
						}
				else
					if(pass[m][n-1])   //左一格走过
						if(maze[m-1][n] == 1)   //上一格是墙
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
							if(pass[m-1][n])    //上一格走过
							{
								if(ptr->back != NULL)
								{
									ptr = ptr->back;
									free(ptr->next);
									ptr->next = NULL;
								}
								m = ptr->m;
								n = ptr->n;
							}
							else
							{
								m-=1;    //往上一格
								ptr->next = (pointer)malloc(sizeof(node));
								ptr->next->m = m;
								ptr->next->n = n;
								preptr = ptr;
								ptr->next->next = NULL;
								pass[m][n] = true;
								ptr = ptr->next;
								ptr->back = preptr;
							}
					else
					{
						n-=1;    //往左一格
						ptr->next = (pointer)malloc(sizeof(node));
						ptr->next->m = m;
						ptr->next->n = n;
						preptr = ptr;
						ptr->next->next = NULL;
						pass[m][n] = true;
						ptr = ptr->next;
						ptr->back = preptr;
					}
			else
				if(pass[m][n+1])      //右一格走过
					if(maze[m][n-1] ==1)   //左一格是墙
						if(maze[m-1][n] == 1)   //上一格是墙
						{
							if(ptr->back != NULL)
							{
								ptr = ptr->back;
								free(ptr->next);
								ptr->next = NULL;
							}
							m = ptr->m;
							n = ptr->n;
						}
						else
							if(pass[m-1][n])    //上一格走过
							{
								if(ptr->back != NULL)
								{
									ptr = ptr->back;
									free(ptr->next);
									ptr->next = NULL;
								}
								m = ptr->m;
								n = ptr->n;
							}
							else
							{
								m-=1;    //往上一格
								ptr->next = (pointer)malloc(sizeof(node));
								ptr->next->m = m;
								ptr->next->n = n;
								preptr = ptr;
								ptr->next->next = NULL;
								pass[m][n] = true;
								ptr = ptr->next;
								ptr->back = preptr;
							}
					else
						if(pass[m][n-1])   //左一格走过
							if(maze[m-1][n] == 1)   //上一格是墙
							{
								if(ptr->back != NULL)
								{
									ptr = ptr->back;
									free(ptr->next);
									ptr->next = NULL;
								}
								m = ptr->m;
								n = ptr->n;
							}
							else
								if(pass[m-1][n])    //上一格走过
								{
									if(ptr->back != NULL)
									{
										ptr = ptr->back;
										free(ptr->next);
										ptr->next = NULL;
									}
									m = ptr->m;
									n = ptr->n;
								}
								else
								{
									m-=1;    //往上一格
									ptr->next = (pointer)malloc(sizeof(node));
									ptr->next->m = m;
									ptr->next->n = n;
									preptr = ptr;
									ptr->next->next = NULL;
									pass[m][n] = true;
									ptr = ptr->next;
									ptr->back = preptr;
								}
						else
						{
							n-=1;    //往左一格
							ptr->next = (pointer)malloc(sizeof(node));
							ptr->next->m = m;
							ptr->next->n = n;
							preptr = ptr;
							ptr->next->next = NULL;
							pass[m][n] = true;
							ptr = ptr->next;
							ptr->back = preptr;
						}
				else
				{
					n+=1;    //往右一格
					ptr->next = (pointer)malloc(sizeof(node));
					ptr->next->m = m;
					ptr->next->n = n;
					preptr = ptr;
					ptr->next->next = NULL;
					pass[m][n] = true;
					ptr = ptr->next;
					ptr->back = preptr;
				}
		else
		{
			m+=1;    //往下一格
			ptr->next = (pointer)malloc(sizeof(node));
			ptr->next->m = m;
			ptr->next->n = n;
			preptr = ptr;
			ptr->next->next = NULL;
			pass[m][n] = true;
			ptr = ptr->next;
			ptr->back = preptr;
		}
		dc.BitBlt(lastn*40,lastm*40,40,40,mdc,0,0,WHITENESS);
		dc.BitBlt(ptr->n*40,ptr->m*40,40,40,mdc,0,0,SRCCOPY);
		if(ptr->back == NULL)
		{
			dc.TextOut(120,320,"找不到出口");
			search = false;
		}
		if(maze[m][n] == 3)
		{
			dc.TextOut(120,320,"找到出口");
			search = false;
		}
}
int canvasFrame::OnCreate(LPCREATESTRUCT lpCreateStruct) 
{
	if (CFrameWnd::OnCreate(lpCreateStruct) == -1)
		return -1;	
	SetTimer(1,100,NULL);	
	return 0;
}

void canvasFrame::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) 
{
	CClientDC dc(this);
	if(nChar == VK_ESCAPE)
		PostMessage(WM_CLOSE);
	if(nChar == VK_F1)
	{
		start = true;
		search = true;
		go = false;
		for(i=0;i<=8;i++)      //清空数组
			for(j=0;j<=8;j++)
				pass[i][j] = false;
		dc.BitBlt(ptr->n*40,ptr->m*40,40,40,mdc,0,0,WHITENESS);
		while(ptr->back)       //删除节点
		{
			ptr = ptr->back;
			free(ptr->next);
			ptr->next = NULL;
		}
		m = ptr->m;
		n = ptr->n;
	}
	if(nChar == VK_F2)
	{
		if(ptr->back == NULL)
		 dc.TextOut(120,320,"此迷宫无出口");
		else
		{
			ptr = first;       //移动指针到第一个节点
			go = true;
			search = false;
		}
	}
	CFrameWnd::OnKeyDown(nChar, nRepCnt, nFlags);
}