typedef struct{
int ord//通道块的路径上的序号
PosType seat//通道块在迷宫的坐标位置
int di//从此通道块走向下一个通道块的方向
}SelemType//stack的元素类型
Status MazePath(MazeType maze,PosType start,PosType end){
//若迷宫 maze中存在从入口start到出口end的通道,所以,求得一条存放在stack中
//(从stack底到顶)并返回TRUE,否则返回FALSE
InitStack(S)
curpos=start//设置当前的位置为入口位置
curstep=1//探索第一步
do{
if(Pass(curpos)){//当前位置可以通过,即是未曾走过的通道块
FootPrint(curpos)//留下足迹
e=(curstep,curpos,1)
Push(s,e)//加入路径
if(curpos==end)
return(TRUE)//到达终点
curpos=NextPos(curpos,1)//下一位置是当前位置的东部
curstep++//探索下一步
}
else{//当前位置不能通过
if(!StackEmpty(S)){
Pop(S,e)
while(e.di==4&&!StackEmpty(S)){
MarkPrint(e.seat)//留下不能通过的标记,并退回一步
Pop(S,e)
}
if(e.di<4){
e.di++
Push(s.e)//换下一个方向探索
curpos=NextPos(e.seat e.di)//设定当前位置是该新方向上的相邻块
}//if
}//if
}//else
}while(!StackEmpty(S))
return(FALSE)
}//MazePath
另外,虚机团上产品团购,超级便宜
本程序的前提是将迷宫保存在一个二维数组里,可走的地方为0,不可走的地方为1。由于采用回朔算法,不使用递归,所以首先应该建立一个栈来保存路径,路径是用一个一个点来表示的,也就是说栈中保存的是一系列点的列表。栈节点类型说明:
struct StackNode
{
POINT Point
struct StackNode *Next, *Prev//双向链表形式
}
栈结构用一个类(CPointStack)实现,声明如下:
class CPointStack
{
public:
void ClearStack()//清空栈
void InitStack()//初始化栈
bool Pop(POINT &pt)//d出顶端元素,并给出该点的坐标,返回是否d出成功
bool Push(POINT pt)//将pt点的信息压入栈,返回是否压入成功
CPointStack()
virtual ~CPointStack()
protected:
StackNode *m_psnTop//栈顶指针
StackNode m_snBottom//栈底,不保存点信息
}
以下为成员函数实现,都是一些数据结构的 *** 作,应该没什么好说的:
//构造时初始化栈
CPointStack::CPointStack()
{
InitStack()
}
//析构时清空栈
CPointStack::~CPointStack()
{
ClearStack()
}
//将点压入栈(成功返回true,失败返回false)
bool CPointStack::Push(POINT pt)
{
StackNode* NewNode = new StackNode
//是否返回true主要看这里申请内存是否成功
if(!NewNode)
return false
NewNode->Point = pt
NewNode->Prev = m_psnTop
NewNode->Next = NULL
m_psnTop->Next = NewNode
m_psnTop = NewNode
return true
}
//将点d出栈(成功返回true,栈为空则返回false)
bool CPointStack::Pop(POINT &pt)
{
if(m_psnTop == &m_snBottom)//是否返回true主要看这里栈是否为空
return false
StackNode *p
p = m_psnTop
m_psnTop = m_psnTop->Prev
pt = p->Point
delete p
m_psnTop->Next = NULL
return true
}
//初始化栈
void CPointStack::InitStack()
{
m_psnTop = &m_snBottom
m_snBottom.Next = NULL
m_snBottom.Prev = NULL
}
//清空栈
void CPointStack::ClearStack()
{
StackNode *p
while(m_psnTop != &m_snBottom)
{
p = m_psnTop
m_psnTop = m_psnTop->Prev
delete p
}
}
接下来设计怎样走出这个迷宫,也就是迷宫算法的主体部分。再次用一个类实现。
在设计这个类时,我考虑到以下几点:
1、迷宫入口和出口的坐标
2、保存迷宫的2维数组
3、获得路径的函数
但是实际设计时由于没有考虑太多问题,只是以设计迷宫算法和解决一个具体迷宫为目的,所以没有考虑动态大小的迷宫,而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识(在保存迷宫数据的表中设置经过的点为2而将死路点设置为3)。
这样迷宫类(CGoMaze)的声明为:
class CGoMaze
{
public:
void Go()//寻找路径的函数
POINT m_ptIn//入口坐标
POINT m_ptOut//出口坐标
BYTE m_btArrMaze[401][601]//保存迷宫的二维表
CGoMaze()
virtual ~CGoMaze()
}
最后让我们来看一下CGoMaze::Go()这个函数:
我们模仿人走迷宫时的思路,设置一个当前点,一个目标点(下一个要走的点)。初始情况下当前点为入口,终止条件为当前点为出口,这样,我们的函数大概结构就出来了。
在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断,当发现任一个方向是未走过的区域时,就将当前点指向那个点进行尝试,同时将当前点入栈并做标记。而当4个方向都不通或已走过时,则为死路,标记当前点为死路并从栈中d出上一个点继续进行尝试,这时因为当前点已被标记为死路,则d出上一个点时就不会重复这条路,达到寻找正确路径的效果。
Go函数的具体实现如下,其实挺简单的^_^:
void CGoMaze::Go()
{
CPointStack psPath//保存路径的栈
POINT ptCur = m_ptIn, ptNext//设置当前点为入口
while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出
{
ptNext = ptCur//设置目标点为当前点,便于下面偏移
if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)
ptNext.y --//如果上方是空的,则目标点向上偏移
else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)
ptNext.x --//如果左边是空的,则目标点向左偏移
else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)
ptNext.y ++//如果下方是空的,则目标点向下偏移
else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)
ptNext.x ++//如果右边是空的,则目标点向右偏移
else
{//这里是没有路的状态
m_btArrMaze[ptCur.y][ptCur.x] = 3//标记为死路
psPath.Pop(ptCur)//d出上一次的点
continue//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2//标记当前点为路径上的点
psPath.Push(ptCur)//当前点压入栈中
ptCur = ptNext//移动当前点
}
}
其实这个部分可以将栈设置为CGoMaze类的成员,然后在Go函数里加上:
psPath.ClearStack()
这样就可以用Timer来演示走迷宫的过程了
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)