数据结构迷宫求解

【完成题目3］迷宫求解

【问题描述】

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，

对任意设定的迷宫，求出一条从入口到出口的通路，或者得出没有通路的结论。

【基本要求】

首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组

（i,j,d）的形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

【算法设计】

本实验的目的是设计一个程序，实现手动或者自动生成一个nXm矩阵的迷宫，寻觅一

条从入口点到出口点的通路。我们将其简化成具体实验内容如下：

选择手动或者自动生成一个nXm的迷宫，将迷宫的左上角作入口，右下角作出口，设

“0”为通路，“1”为障碍，即无法穿越。假设从起点出发，目的为右下角终点，可向''上、

下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代

表“1”，用“口”代表“0”，用“一”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图

以及迷宫行走路径。如果迷宫为死迷宫，输出信息。

可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷

宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

本程序包含三个模块

1）主程序模块：

voidmain（）

（

初始化；

do{

接受命令；

处理命令；

}while（命令！=退出）；

}

2）栈模块一一实现栈抽象数据类型；

3）迷宫模块一一实现迷宫抽象数据类型。

【源代码】

#include<stdlib.h>〃库中包含和randO函数

#include<stdio.h>//c语言里的库

#include<iostream>

8include<malloc.h>

#defineOK1

#defineERROR0

^defineSTACK_INIT_SIZE100

^defineSTACKINCREMENT10

^defineOVERFLOW-1

#defineM49

^defineN49

usingnamespacestd;

intmaze[M][N];

typedefintStatus;

typedefstruct

{

intm,n,direc;

(MazeType,*LMazeType;

typedefstruct

(

LMazeTypetop;

LMazeTypebase;

intstacksize;

intover;

}Stack;

voidInit_hand_Maze(intmaze[M][N],intm,intn)

{

inti,j;

for(i=l;i<=m+l;i++)

for(j=l;j<=n+l;j++)

(

maze[i][j]=l;

)

请按行输入迷宫，0表示通路，1表示障碍

for(i=l;i<m+l;i++)

for(j=l;j<n+l;j++)

cin»maze[i][j];

for(i=l;i<m+l;i++)

(

for(j=l;j<n+l;j++)

(

if(maze[i][j]!=0&&maze[i][j]!=1){

您输入有误，请重新输入

Init_handMaze(maze,m,n);

}

}

)

)

voidInit_automaticMaze(intmaze[M][N],intm,intn)〃自动生成迷客

2/11

inti,j;

迷宫生成中

for(i=l;i<m+l;i++)

for(j=l;j<n+l;j++)

maze[i][j]=rand()%2;〃随机生成0、1

)

voidPrintMaze(intmaze[M][N],introw,intcol)

{

inti,j;

迷宫如图所示

for(i=l;i<row+l;i++)

(

for(j=l;j<col+l;j++)

(

if(mazeti][j]=D

■

else

□

)

cout«endl;

)

)

StatusInitStack(Stack&S)

{

S.base=(LMazeType)malloc(STACK_INIT_SIZE*sizeof(MazeType));

if(!S.base)exit(OVERFLOW);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

S.over=0;

returnOK;

)

StatusPush(Stack&S,MazeTypee)

(

if(S.top-S.base〉二S.stacksize)

(

S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT)sizeof(MazeType));

if(!S.base)exit(OVERFLOW);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

3/11

)

StatusPop(Stack&S,MazeType&e)

{

if(S.top二二S.base)returnERROR;

e=*-S.top;

returnOK;

)

StatusMazePath(Stack&S,MazeType&e,intmaze[M][N],intm,intn)

{

do

(

if(maze[e.m][e.n]=0)//0可通，1不可通，2为已走过

{

Push(S,e);

maze[e.m][e.n]=2;

if(e.m=二m&&e.n==n)

(

S.over=l;〃表示存满一条路径

returnOK;

)

else{

e.n++;

e.direcR;〃来这一点时的方向，0右1下2左3上

MazePath(S,e,maze,m,n);

)

)

else

(

if(S.top!=S.base&&S.over!=l)

(

switch(e.direc)〃回到上一位置并同时改变方向走下一步

(

case0:

e.n—;

e.m++;

e.direc=l;

break;

case1:

e.m—;

e.n——；

e.direc=2;

break;

case2:

e.n++;

4/11

e.m——；

e.direc=3;

break;

case3:

Pop(S,e);

break;

)

)

)

}while(S.top!=S.base&&S.over!=l);

returnOK;

)

intPrintPath(StackS,intmaze[M][N],introw,intcol)

(

if(S.top==S.base)

I

此迷宫无解

returnERROR;

}

MazeTypee;

while(S.top!=S.base)

(

Pop(S,e);

maze[e.m][e.n]=(e.direc+10);

)

完成

路径为

inti,j;

for(i=l;i<row+l;i++)

(

for(j=l;j<col+l;j++)

(

switch(maze[i][j])

(

case0:

□

break;

case1:

■

break;

case2:

5/11

break;

case10:

break;

case11:

I

break;

case12:

break;

case13:

t

break;

}

)

cout«endl;

)

入口

完成

returnOK;

)

intmain()

(

inti,m,n,maze[M][N],eye1e=0;

while(cycle!=(-l))

欢迎进入迷宫求解系统

cout<<endl;

☆1手动生成迷宫☆

☆2自动生成迷宫☆

☆3退出☆

请选择你的操作：

cin»i;

switch(i)

(

case1:

请输入行数：

cin»m;

6/11

请输入列数:

cin»n;

while((m<l||m>49)I|(n<lI|n>49))

(

抱歉，你输入的行列数超出预设范围(1-49,1-49),请重新输入：

请输入行数：

cin»m;

请输入列数：

cin»n;

}

InithandMaze(maze,m,n);

PrintMaze(maze,m,n);

MazeTypestart,end;

请输入起点

cin»start.m»start.n;

start.direc=O;

请输入终点

cin»end.m»end.n;

StackS;

寻觅路径

InitStack(S);

MazePath(S,start,maze,end.m,end.n);

PrintPath(S,maze,m,n);

getcharO;

while(getcharO');〃接受一个输入，当为回车时执行break跳出，否则向来执行

接受数据

break;

case2:

请输入行数：

cin>>m;

请输入列数：

cin»n;

while(6n<0||m>49)||(n<0jn>49))

(

抱歉，你输入的行列数超出预设范围(0-49,0-49),请重新输入：

请输入行数：

cin»m;

7/11

请输入列数:

cin»n;

}

Init_automatic_Maze(maze,m,n);

PrintMaze(maze,m,n);

请输入起点

cin»start.m»start.n;

start.direc=O;

请输入终点

cin»end.m»end.n;

寻觅路径

InitStack(S);

MazePath(S,start,maze,end.m,end.n);

PrintPath(S,maze,m,n);

getchar();

while(getchar()I-');

break;

case3:

cycle=(-1);break;

default:

你的输入有误

getchar();

while(getchar()!=，');

break;

)

)

【结果截图】

8/11

请选择你的操作,

向前人行数：3

请箱入列数，3

谓也什辆人迷宫,8表示通路,［表示璋碍:

B11

101

110

W宫如图所示.

请输入起点mn：

13

请输入终点mn:

31

寻找路径--

=■■■■■■■■■■■■=■■■=■■at।

此迷宫无解

请按任意键继续...-

迷宫无解的情况

9/11

欢迎进入迷宫求解系统

$;$

☆3退出☆

?选择你的性作;

情输入行数：3

通输入列数।3

青攫行输入迷宫，。表示通路,［表示障碍:

H01

100

100

迷宫如图所示.

请输入起点en：

11

请输入终点•*•»：

33

寻找路径...

完成，

T

入■A口

元成，

请按任意键继续.・・

手动生成迷宫的情况