Question

C++设计一个迷宫并走出来

设计一个迷宫游戏，给定迷宫的入口。如果存在出口，程序能够显示行走的路径，并最终到达出口，并输出“成功走出迷宫”；如果不存在出口，程序也能够显示行走的过程，并最终回退到入口，并输出“回退到入口”。
1.定义一个二维数组(MxN)表示一个迷宫，数组的元素为“#”或“.”， “#”表示迷宫里的墙，“.”表示可以通行的过道。从入口进入迷宫后，只能沿着“.”所代表的位置移动。
2.定义一个函数，用于生成任意大小的迷宫（即数组的宽度和高度由用户输入），要求生成的迷宫至少有一个不同于入口的出口。
3.定义一个递归函数，用于实现走迷宫。该函数的形参应该包括表示迷宫的二维数组和迷宫的入口。函数中用字符‘X’表示已走过的路径，并输出每向前移动一步后迷宫的状态。
void mazeGenerator ( char **&mg ,int n, int m)
{
srand((unsigned)time(NULL));
int i,j;
mg = new char*[m];
for ( i=0;i<n;i++)
{
mg[i]=new char[n];
}
for (i = 0; i < n; i++)
for(j= 0; j < m; j++)
mg[i][j] = rand()%2?'#':'.' ;
} /*这是用来生成迷宫的函数，可是一定要有出口不知道怎么弄。也不知道怎样用递归走迷宫。请高手帮帮忙啊！！*/

Answer 1

本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。
栈节点类型说明：
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来演示走迷宫的过程了

Answer 2

这么生成的迷宫有71.428571……种可能根本走不通。。。。。。。。。。汗……

Answer 3

我记得严蔚敏版的《数据结构》这本书里面就有关于解迷宫的算法，你可以看看。