C++设计一个迷宫并走出来11
发布网友
发布时间：2023-10-20 05:36
共3个回答
热心网友
时间：2024-12-02 21:59
栈节点类型说明：
struct StackNode
{
POINT Point;
struct StackNode *Next, *Prev;//双向链表形式
};
栈结构用一个类（CPointStack）实现，声明如下：
class CPointStack
{
public:
void ClearStack();//清空栈
void InitStack();//初始化栈
bool Pop(POINT &pt);//弹出顶端元素，并给出该点的坐标，返回是否弹出成功
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;
}
//将点弹出栈(成功返回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个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。
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);//弹出上一次的点
continue;//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2;//标记当前点为路径上的点
psPath.Push(ptCur);//当前点压入栈中
ptCur = ptNext;//移动当前点
}
}
其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：
psPath.ClearStack();
这样就可以用Timer来演示走迷宫的过程了
热心网友
时间：2024-12-02 22:00
热心网友
时间：2024-12-02 22:00
