基于栈实现的迷宫问题.doc

基于栈实现的迷宫问题

1、问题描述：
在一个二维阵列构成的迷宫里, 数组元素仅有0和1构成，其中 0表示可通行的路径, 1代表障碍。另外，定义左上角是迷宫的入口, 右下角是迷宫的出口, 在迷宫里面只允许上下左右四个方向行走，请找出一条通路。

2、算法基本思想：
由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中采用“栈”进行求解。
2.1、迷宫构建：
为了避免每走一步便需判断是否走出迷宫的麻烦，将所创建的迷宫用1包围起来。
2.2、位置搜索：
每到一处，总让它按上、下、左、右4个方向试探下一个位置；如果某方向可以通过，即该方向上的元素为0，则前进一步，并在新位置上继续进行搜索；如果4个方向都走不通或曾经走过，则后退一步，在原来的位置上继续试探下一位置。
每前进一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。

3、算法运行环境：
VC++6.0

4、主要函数：
Mazepath函数：
求解迷宫maze中,从入口start到出口end的一条路径
若存在,返回TRUE,否则返回FALSE
InitMaze函数：
创建初始矩阵
按照用户输入的数据构建0/1矩阵，并在矩阵四周添加一圈1作为围墙。
Pass函数：
判断当前节点能否通过。
FootPrint函数：
对于走过的节点用 '*' 进行标记。
MarkPrint函数：
对于不能通过的节点用 '#' 进行标记。
Nextpos函数;
返回当前节点的下一结点，对应东、西、南、北四个方向。
Printmaze 函数：
打印迷宫信息，存在的通路用 '*' 表示。

5、算法举例：

5.1、输入的矩阵：

运行结果：

5.2、输入的矩阵：

运行结果：
没有找到通路

6、 算法复杂度分析：（n为迷宫的行数，m为迷宫的列数）
走迷宫的时间复杂度：O(n*m*2)。

附迷宫问题源程序
//base.h
#include
#include
#include
#include
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//函数的返回值
typedef int Status;
//下一个通道方向
typedef int DirectiveType;

//stack.h
//迷宫大小
#define RANGE 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

//------------ 栈的顺序存储实现 ------------------------------
typedef struct
{
int row;
int col;
}PosType;
typedef struct
{
int step; //当前位置在路径上的\"序号\"
PosType seat; //当前的坐标位置
DirectiveType di; //往下一个坐标位置的方向
}SElemType;
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

//----------------- 栈的基本操作的算法实现 --------------------------------
Status InitStack(SqStack &s)
{
s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!s.base)
exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack s, SElemType &e )
{
if( s.top == s.base)
return ERROR;
e = *(s.top-1);
return OK;
}
Status Push(SqStack &s, SElemType e)
{

if(s.top-s.base >= s.stacksize)
{ //栈满，追加存储空间
s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!s.base)
exit(OVERFLOW);
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
s.top++ = e;
return OK;
}
Status Pop(SqStack &s, SElemType &e)
{
if(s.top==s.base)return ERROR;
e = * --s.top;
return OK;
}
int StackEmpty(SqStack s)
{
return s.base == s.top;
}
Status ClearStack(SqStack &s)
{
s.top = s.base;
return OK;
}

//maze.h

#define ROW 9 //迷宫的行数
#define COL 8 //迷宫的列数
typedef struct
{
int m,n;
int arr[RANGE][RANGE];
}MazeType; //迷宫类型
Status InitMaze(MazeType &maze, int a[][COL], int row, int col)
{
//按照用户输入的row行和col列的二维数组(0/1)
//设置迷宫maze的初值,包括加上边缘一圈的值
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
maze.arr[i][j] = a[i-1][j-1];
}
}
//加上围墙
for(int j=0;j<=col+1;j++)
{
maze.arr[0][j] = maze.arr[row+1][j]=1;
}
for(i=0;i<=row+1;i++)
{
maze.arr[i][0] = maze.arr[i][col+1]=1;
}
maze.m = row, maze.n = col;
return OK;
}
Status Pass(MazeType maze,PosType curpos)
{
//判断当前节点是否通过
return maze.arr[curpos.row][curpos.col] == 0;
}
Status FootPrint(MazeType &maze,PosType curpos)
{
//留下足迹
maze.arr[curpos.row][curpos.col]='*';
return OK;
}
Status MarkPrint(MazeType &maze,PosType curpos)
{
//留下不能通过的标记
maze.arr[curpos.row][curpos.col]='#';
return OK;
}
SElemType CreateSElem(int step, PosType pos, int di)
{
SElemType e;
e.step = step;
e.seat = pos;
e.di = di;
return e;
}
PosType NextPos(PosType curpos, DirectiveType di)
{ //返回当前节点的下一节点
PosType pos = curpos;
switch(di)
{
case 1: //东
pos.col++; break;
case 2: //南
pos.row++; break;
case 3: //西
pos.col--; break;
case 4: //北
pos.row--; break;
}
return pos;
}

void PrintMaze(MazeType maze,int row,int col)
{
//打印迷宫信息
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
switch(maze.arr[i][j])
{
case 0:
printf(" "); break;
case '*':
printf("*"); break;
case '#':
printf("#"); break;
case 1:
printf("#"); break;
}
}
printf("\n");
}
}
Status MazePath(MazeType &maze,PosType start, PosType end,PosType *a,int *m)
{ //求解迷宫maze中,从入口start到出口end的一条路径
//若存在,返回TRUE,否则返回FALSE
SqStack s;SElemType e;
InitStack(s);
PosType curpos = start;
int curstep = 1;
//探索第一部
do
{
if( Pass(maze,curpos) )
{
//如果当前位置可以通过,即是未曾走到的通道块
FootPrint(maze,curpos); //留下足迹
e = CreateSElem(curstep,curpos,1); //创建元素
Push(s,e);
a[*m].row=curpos.row;
a[*m].col=curpos.col;
++(*m); //将该元素的的行号和列号存入
数组中，并通过指针path返回

if( curpos.row==end.row && curpos.col==end.col )
return TRUE;
else
{
curpos =NextPos(curpos,1); //获得下一节点:当前位置的东邻
curstep++; //探索下一步
}
}
else
{
//当前位置不能通过
if(!StackEmpty(s))
{
Pop(s,e);
while(e.di==4 && !StackEmpty(s) )
{
MarkPrint(maze,e.seat);
Pop(s,e);curstep--; //留下不能通过的标记,并退回一步
--(*m); //数组序号减1，该元素被删除。
}
if(e.di<4)
{
e.di++;
Push(s,e); //换一个方向探索
curpos = NextPos(e.seat,e.di); /求下一个节点
}
}
}
}
while(!StackEmpty(s));
return FALSE;
}

void main()
{
int a[ROW][COL],b=0,*m;
m=&b;
printf("enter the maze’s data:(9行8列) ");
for(int i=0;i
start.row = 1;start.col=1;
end.row = 9; end.col = 8;
MazeType maze;
InitMaze(maze,a,ROW,COL);
Status ok = MazePath(maze,start,end,path,m);

if(ok)
{
PrintMaze(maze,ROW,COL); //打印出迷宫图形
int i=0;
while(i<(*m)) //输出路径
{
printf("\n第%d步：第%d行，第%d列",i+1,path[i].row,path[i].col);
i++;
}
}
else
printf("没有找到通路");
}