VC迷宫问题分析关键字 VC迷宫问题分析VC实例：迷宫问题同学们好! 今天由我给大家讲一个VC实例：迷宫问题。学过算法的人就知道迷宫问题是一个经典的算法问题。当然，我们今天的内容不是回朔，也不是递归。我们今天的主要内容有两个：一，用纯C++处理迷宫问题时如何让结构更加优良，二，如何用MFC类库处理输入和输出。 结构设计什么是迷宫问题呢？假定有一个长方形的地图，长m单位，宽n单位，可以人为地将此迷宫划分成m*n小块，每小块只能有两种状态：可以通过或不能通过。给定一个起点和一个终点，求出一条路径(本实例中，假定起点为左上角，终点为右上角)。 要完整描述地图类，至少要三个变量，长、宽、每一小块的状态。本实例中，长用int形的m_iColNum用表示，宽用int形的m_iRowNum表示，每一小块的状态由int**的m_pMapData。由于长宽是未知的，所以只能用动态数组表示各小块的状态。为什么用int**，而不用bool**呢？bool**节省内存，但现在的内存以G计算，几字节乃至几十字节都没必要计较。用int**有良好的扩充性。同学们，想一想，在复杂一个非常复杂的迷宫问题中，每一小块还有那些状态？(等学生们回答，并加以总结)在一个复杂的迷宫问题，每一小块可能有许多状态，如高山，森林，河流，门（开启）、门（关闭）等。如果我们用CMazeMap类来处理迷宫信息，根据上面的分析，它有三个成员变量。下面我们来分析，这个类至少要有几个成员函数？下面分别说明。 void ChangeRowCol(int iRow ,int iCol); 改变行列数，会重新分配内存并复制数据。行数或列数变小时，会丢失部分数据。 void CopyData(const CMazeMap& other); 复制数据，不改变行列号。当源地图和目的地图的行列数不等是，要尽可能多的复制数据。下面举例说明：当源地图有5行4列，目的地图有4行5列时，只能复制4行4列。 int** CreateInitData(); 根据m_iRowNum和m_iColNum为动态二维数组m_pMapData分配空间。如果要重复调用此函数，请先调用ReleaseData函数。 bool IslegalRowCol(int iRow,int iCol); 判断行列号是否非法。 void ReleaseData(); 释放动态二维数组m_pMapData所占内存。 bool SearchPath(); 查找路径，并打上标记。0表示不能通过，1表示能通过但不在行走路线上，2表示在行走路线上。此函数分三步：先清除行走路线标志，再寻找合适的路径，最后为行走路线打标志。 构造、设置、取得函数就不列出来了。设置行列的时候注意，必须限制最小行列数和最大行列数，以减少错误的发生。 为了体会到具体的寻路过程，我们回想一下我们在生活中是如何寻路的。尝试移动（东移南移西移北移），如果无路可走，则退一步。为了不昏头，尝试的顺序是固定的，如：先右再下再左再上。我们用CSearchPath类来处理查找路径，它有五组成员变量: CMazeMap型的m_map记录地图信息；int型的m_iStep记录步数；int型的m_rowSet[1000]记录每步所在的行；int型的 m_colSet[1000] 记录存放每步的列; int型的m_iMoveType记录每步的移动方式。成员函数有三个: bool Back(); 当前无路可走，返上一步所在位置。 bool Move(int iType); 移动（右移下移左移上移） bool Search(); 查找每第一条路径，内部调用Back函数和Move函数。 输入输出处理上面的功能纯C++都可以完成，输入输出也可以用纯C++来处理，但没有VC++方便。如果用纯C++处理界面也方便，那学VC就没多大意义了。 一，输入功能。用户可以通过鼠标单击改变每一块的状态。无法通过的块单击后变成可以通过的块，反之亦然。CMazeMap::ChangeMapState处理此功能，原型为CRect ChangeMapState(CRect r,CPoint pt)，返回值是点击的小块的范围，r是迷宫的范围，pt是鼠标单击的坐标。每次改变小块的状态，都重新查找路径并显示出来。改变行列数比较简单，所以本实例写死算了。 二，输出功能。视图分成若干小块，与迷宫的小块相对应。如果此小块无法通过则显示成红色小块；如果小块可能通过但不在移动路线上，则显示成绿色小块；如果此小块在移动路线上，则显示成蓝色小块。CMazeMap::Draw处理此功能，其原型为void Draw(CDC* pDC,CRect r)，pDC是设备相关类的指针，r是迷宫的范围。
|
||||||