c语言实现 迷宫问题

数据结构试验——迷宫问题

数据结构试验——迷宫问题

（一）基本问题

1.问题描述

这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。

简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。

入口出口

图1 迷宫示意图

迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清晰，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。

2.数据结构设计

以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下

int mg[M+2][N+2]= {

{1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1}

};在算法中用到的栈采用顺序存储结构，将栈定义为 Struct

{ int i; //当前方块的行号 int j; //当前方块的列号

int di; //di是下一个相邻的可走的方位号

数据结构试验——迷宫问题

}st[MaxSize];// 定义栈 int top=-1 //初始化栈

3设计运算算法

要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。

方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。

move[4] 0 1 2 3 x -1 0 1 0 y 0 1 0 -1 图2数组move[4]

方位示意图如下：

通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。

（1）下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为—1），在栈不空时循环——取栈顶方块（不退栈）①若该

数据结构试验——迷宫问题

方块为出口，输出所有的方块即为路径，其代码和相应解释如下： int mgpath(int xi,int yi,int xe,int ye) //求解路径为:(xi,yi)->(xe,ye) {

struct {

int i; //当前方块的行号 int j; //当前方块的列号

int di; //di是下一可走方位的方位号 } st[MaxSize]; //定义栈

int top=-1; //初始化栈指针 int i,j,k,di,find;

top++; //初始方块进栈 st[top].i=xi;st[top].j=yi; st[top].di=-1;mg[1][1]=-1;

while (top>-1) //栈不空时循环 {

i=st[top].i;j=st[top].j;di=st[top].di; //取栈顶方块 if (i==xe && j==ye) //找到了出口,输出路径 {

printf(\迷宫路径如下:\\n\ for (k=0;k<=top;k++) {

printf(\

if ((k+1)%5==0) //每输出每5个方块后换一行 printf(\ }

printf(\ return(1); //找到一条路径后返回1 }

②否则，找下一个可走的相邻方块若不存在这样的路径，说明当前的路径不可能走通，也就是恢复当前方块为0后退栈。若存在这样的方块，则其方位保存在栈顶元素中，并将这个可走的相邻方块进栈（其初始位置设置为-1） 求迷宫回溯过程如图4所示

数据结构试验——迷宫问题

从前一个方块找到相邻可走方块之后，再从当前方块找在、相邻可走方块，若没有这样的方快，说明当前方块不可能是从入口路径到出口路径的一个方块，则从当前方块回溯到前一个方块，继续从前一个方块找可走的方块。

为了保证试探的可走的相邻方块不是已走路径上的方块，如（i,j）已经进栈，在试探（i+1，j）的下一方块时，又试探道（i，j），这样会很悲剧的引起死循环，为此，在一个方块进栈后，将对应的mg数组元素的值改为-1（变为不可走的相邻方块），当退栈时（表示该方块没有相邻的可走方块），将其值恢复0，其算法代码和相应的解释如下： find=0; while (di<4 && find==0) //找下一个可走方块 { di++; switch(di) { case 0:i=st[top].i-1;j=st[top].j;break; case 1:i=st[top].i;j=st[top].j+1;break; case 2:i=st[top].i+1;j=st[top].j;break; case 3:i=st[top].i,j=st[top].j-1;break; } if (mg[i][j]==0) find=1;//找到下一个可走相邻方块 } if (find==1) //找到了下一个可走方块 { st[top].di=di; //修改原栈顶元素的di值 top++; //下一个可走方块进栈 st[top].i=i;st[top].j=j;st[top].di=-1; mg[i][j]=-1; //避免重复走到该方块 } else //没有路径可走,则退栈

数据结构试验——迷宫问题

{ mg[st[top].i][st[top].j]=0;//让该位置变为其他路径可走方块 top--; //将该方块退栈 } } return(0); //表示没有可走路径,返回0 （2）求解主程序

建立主函数调用上面的算法，将mg和st栈指针定义为全局变量 void main() { mgpath(1,1,M,N); }

3界面设计

设计很简单的界面，输出路径

4运行结果

图5。基本运行结果

（二）8个方向的问题

1.设计思想

(1)设置一个迷宫节点的数据结构。 (2)建立迷宫图形。

数据结构试验——迷宫问题

(3)对迷宫进行处理找出一条从入口点到出口点的路径。 (4)输出该路径。 (5)打印通路迷宫图。

初始化迷宫 通过随机方法设置迷宫布局 建立并输出迷宫原图 搜索迷宫通路 输出迷宫通路及路线图 结束 图6功能结构图

当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序号i，j来表示。而从 [i],[j]位置出发可能进行的方向见下图7.如果[i],[j]周围的位置均为0值，则老鼠可以选择这8个位置中的任一个作为它的下一位置。将这8个方向分别记作：E（东）、SE（东南）、S（南）SW（西南）W（西）、NW（西北）、N（北）和NE（东北）。但是并非每一个位置都有8个相邻位置。如果[i],[j]位于边界上，即i=1，或i=m，或j=1，或j=n，则相邻位置可能是3个或5个为了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为maze[m+2],[n+2]在迷宫行进时，可能有多个行进方向可选，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定[i],[j]的下一步位置的坐标是[x],[y]，并将这8个方位伤的x和y坐标的增量预先放在一个结构数组move[8]中（见图8）。该数组的每个分量有两个域dx和dy。

数据结构试验——迷宫问题

例如 要向东走，只要在j值上加上dy，就可以得到下一步位置的[x],[y]值为[i],[j+dy]。于是搜索方向的变化只要令方向值dir从0增至7，便可以从move数组中得到从[i],[j]点出发搜索到的每一个相邻点[x],[y]。

x=i+move[dir].dx y=j+move[dir].dy

dx dy

图7 方向位移图 图8向量差图

为了防止重走原路，我们规定对已经走过的位置，将原值为0改为-1，这既可以区别该位置是否已经走到过，又可以与边界值1相区别。当整个搜索过程结束后可以将所有的-1改回到0，从而恢复迷宫原样。

这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从（E）开始，按顺时针对8个方向进行探测，若某个方位上的maze[x],[y]=0，表示可以通行，则走一步；若maze[x],[y]=1，表示此方向不可通行须换方向再试。直至8个方向都试过，maze[x],[y]均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此需要设置一个栈，用来记录所走过的位置和方向（i，j，dir）。

当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和新的方向重新进栈，并走到新的位置。如果探测到x=m，y=n，则已经到达迷宫的出口，可以停止检测，输出存在栈中的路径；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如

数据结构试验——迷宫问题

果已经退到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。

2系统算法（伪代码描述）：

(1)建立迷宫节点的结构类型stack[]。

(2)入迷宫图形 0表示可以通 1表示不可以通。 用二维数组maze[m+2][n+2]进行存储。

数组四周用1表示墙壁，其中入口点（1，1）与出口点（m，n）固定。 (3)函数path()对迷宫进行处理，从入口开始：

While(!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)&&(maze[x][y]==-1)))

{

For(扫描八个可以走的方向)

{

If(找到一个可以走的方向) {

进入栈

标志在当前点可以找到一个可以走的方向 避免重复选择maze[x][y]=-1 不再对当前节点扫描 }

If(八个方向已经被全部扫描过，无可以通的路)

{

标志当前节点没有往前的路

后退一个节点搜索 } }

If(找到了目的地) {

输出路径退出循环 }

数据结构试验——迷宫问题

}

未找到路径

(4)输出从入口点到出口点的一条路径。 (5)输出标有通路的迷宫图。

3.算法流程图：

开始 初始化迷宫，显示迷宫 初始化方向位移数组 寻找迷宫中的一条出路 dir>=7 或栈空 While 栈不空且dir<7 设1，1为出口 do F F elseIf T dir++ 回退一步 If maze[x][y]==0 T 该点数据入栈 出口或入口 显示通路 结束 图9 算法流程图

数据结构试验——迷宫问题

4.程序代码：

#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/ #define N2 11

#define maxlen M2 // 栈长度 #include #include #include

int M=M2-2,N=N2-2;//M*N迷宫的大小 typedef struct //定义栈元素的类型 { int x,y,dir; }elemtype;

typedef struct // 定义顺序栈 { elemtype stack [maxlen]; int top; }sqstktp;

struct moved //定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move { int dx,dy;};

//////////////////////////////////////////////////////////////////////////////////////////////////// void inimaze(int maze[][N2])////初始化迷宫 { int i,j,num; for(i=0,j=0;i<=M+1;i++)//设置迷宫边界 maze[i][j]=1; for(i=0,j=0;j<=N+1;j++) maze[i][j]=1; for(i=M+1,j=0;j<=N+1;j++) maze[i][j]=1; cout<<\原始迷宫为：\ for(i=1;i<=M;i++) { for (j=1;j<=N;j++) { num=(800*(i+j)+1500) % 327;//根据MN的值产生迷宫 if ((num<150)&&(i!=M||j!=N)) maze[i][j]=1; else maze[i][j]=0; cout<

数据结构试验——迷宫问题

} cout<

/////////////////////////////////////////////////////////////////////////////////////////////////////////////// void inimove(struct moved move[])//初始化方向位移数组

{//依次为East，Southeast，south，southwest，west，northwest，north，northeast move[0].dx=0;move[0].dy=1; move[1].dx=1;move[1].dy=1; move[2].dx=1;move[2].dy=0; move[3].dx=1;move[3].dy=-1; move[4].dx=0;move[4].dy=-1; move[5].dx=-1;move[5].dy-=1; move[6].dx=-1;move[6].dy=0; move[7].dx=-1;move[7].dy=1; }//

void inistack(sqstktp *s) /*初始化栈*/ { s->top=-1;

} /*inistack*/ int push(sqstktp*s,elemtype x) { if(s->top==maxlen-1) return(false); else { s->stack[++s->top]=x;/*栈不满，执行入栈操作*/ return(true); } }/*push*/

elemtype pop(sqstktp *s)/*栈顶元素出栈*/ { elemtype elem; if(s->top<0) //如果栈空，返回空值 { elem.x=NULL; elem.y=NULL; elem.dir=NULL; return(elem); } else { s->top--; return(s->stack[s->top+1]); //栈不空，返回栈顶元素 }

数据结构试验——迷宫问题

} //pop

////////////////////////////////////////////////////////////////////////////////////

void path(int maze[][N2],struct moved move[],sqstktp *s) //寻找迷宫中的一条通路 { int i,j,dir,x,y,f; elemtype elem; i=1;j=1;dir=0; maze[1][1]=-1; //设[1][1]为入口处 do { x=i+move[dir].dx;//球下一步可行的到达点的坐标 y=j+move[dir].dy; if(maze[x][y]==0) { elem.x=i;elem.y=j;elem.dir=dir; f=push(s,elem);//如果可行将数据入栈 if(f==false)//如果返回假，说明栈容量不足 cout<<\栈长不足\ i=x;j=y;dir=0;maze[x][y]=-1; } else if (dir < 7) dir++; else { elem=pop(s); //8个方向都不行，回退 if(elem.x!=NULL) { i=elem.x; j=elem.y; dir=elem.dir+1; } } }while(!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)&&(maze[x][y]==-1))); if(s->top==-1)//若是入口，则无通路 cout<<\此迷宫不通\ else { elem.x=x; elem.y=y; elem.dir=dir;//将出口坐标入栈 f=push(s,elem); cout<<\迷宫通路是：\ i=0; while (i <= s->top) {

//循环 数据结构试验——迷宫问题

cout<<\显示迷宫通路 if(i!=s->top) cout<<\ if((i+1)%4==0) cout<

//////////////////////////////////////////////////////////////////////////////

void draw(int maze[][N2],sqstktp *s) //在迷宫中绘制出通路 { cout<<\逃逸路线为：\ int i,j; elemtype elem; for(i=1;i<=M;i++) //将迷宫中全部的-1值回复为0值 { for(j=1;j<=N;j++) { if(maze[i][j]==-1) maze[i][j]=0; while(s->top>-1) //根据栈中元素的坐标，将通路的各个点的值改为8 { elem=pop(s); i=elem.x;j=elem.y; maze[i][j]=8; } for(i=1;i<=M;i++) { for(j=1;j<=N;j++) { printf(\ //显示已标记通路的迷宫 } cout<

void main() //寻找迷宫通路程序 { sqstktp *s; int maze[M2][N2]; struct moved move[8];

数据结构试验——迷宫问题

}

inimaze(maze); //初始化迷宫数组 s=(sqstktp *)malloc(sizeof(sqstktp));

inistack(s); //初始化栈

inimove(move); //初始化方向位移数组 path(maze,move,s); //寻找迷宫通路 cout<

draw(maze,s); //绘制作出通路标记的迷宫

5.运行结果

（三）求所有通路和最短路径的算法

1.源代码（用原题的数据）

#include #define M 5 #define N 7 #define MaxSize 100 int mg[M+1][N+1]={ {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1},

/*行数*/ /*列数*/

/*栈最多元素个数*/

/*一个迷宫,其四周要加上均为1的外框*/

数据结构试验——迷宫问题

{1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} }; struct { int i;int j;int di;

} Stack[MaxSize],Path[MaxSize]; /*定义栈和存放最短路径的数组*/ int top=-1; /*栈指针*/ int count=1; /*路径数计数*/ int minlen=MaxSize; /*最短路径长度*/ void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1;mg[1][1]=-1; /*初始结点进栈*/ while (top>-1) /*栈不空时循环*/ { i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,输出路径*/ { printf(\ \ for (k=0;k<=top;k++) { printf(\ \ if ((k+1)%5==0) printf(\ /*输出时每5个结点换一行*/ } printf(\ if (top+1

数据结构试验——迷宫问题

case 0:i=Stack[top].i-1;j=Stack[top].j;break; case 1:i=Stack[top].i;j=Stack[top].j+1;break; case 2:i=Stack[top].i+1;j=Stack[top].j;break; case 3:i=Stack[top].i,j=Stack[top].j-1;break; } if (mg[i][j]==0) find=1; } if (find==1) /*找到了下一个可走结点*/ { Stack[top].di=di; /*修改原栈顶元素的di值*/ top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;/*下一个可走结点进栈*/ mg[i][j]=-1; /*避免重复走到该结点*/ } else /*没有路径可走,则退栈*/ { mg[Stack[top].i][Stack[top].j]=0; /*让该位置变为其他路径可走结点*/ top--; } } printf(\最短路径如下:\\n\ printf(\长度: %d\\n\ printf(\路径: \ for (k=0;k

void main() { printf(\迷宫所有路径如下:\\n\ mgpath(); }

2求解结果

数据结构试验——迷宫问题

6.实验收获及思考

这次试验总体来说还是比较简单的，因为几个思考问题都是在基本问题的源代码上进行改进和补充。有了第一次数据结构编程和测试的经验，这次试验减少了很多困难，相对来说容易多了。

附录

基本问题换代码(思考问题源代码在上文中已经全部给出)

#define M 4 #define N 6

#define MaxSize 100 #include int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1},

数据结构试验——迷宫问题

{1,1,1,1,1,1,1,1} };

int mgpath(int xi,int yi,int xe,int ye) //求解路径为:(xi,yi)->(xe,ye) { struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一可走方位的方位号 } st[MaxSize]; //定义栈 int top=-1; //初始化栈指针 int i,j,k,di,find; top++; //初始方块进栈 st[top].i=xi;st[top].j=yi; st[top].di=-1;mg[1][1]=-1; while (top>-1) //栈不空时循环 { i=st[top].i;j=st[top].j;di=st[top].di; //取栈顶方块 if (i==xe && j==ye) //找到了出口,输出路径 { printf(\迷宫路径如下:\\n\ for (k=0;k<=top;k++) { printf(\ if ((k+1)%5==0) //每输出每5个方块后换一行 printf(\ } printf(\ return(1); //找到一条路径后返回1 } find=0; while (di<4 && find==0) //找下一个可走方块 { di++; switch(di) { case 0:i=st[top].i-1;j=st[top].j;break; case 1:i=st[top].i;j=st[top].j+1;break; case 2:i=st[top].i+1;j=st[top].j;break; case 3:i=st[top].i,j=st[top].j-1;break; } if (mg[i][j]==0) find=1;//找到下一个可走相邻方块 } if (find==1) //找到了下一个可走方块

数据结构试验——迷宫问题

{ st[top].di=di; //修改原栈顶元素的di值 top++; //下一个可走方块进栈 st[top].i=i;st[top].j=j;st[top].di=-1; mg[i][j]=-1; //避免重复走到该方块 } else //没有路径可走,则退栈 { mg[st[top].i][st[top].j]=0;//让该位置变为其他路径可走方块 top--; //将该方块退栈 } } return(0); //表示没有可走路径,返回0 }

void main() { mgpath(1,1,M,N); }

本文来源：https://www.bwwdw.com/article/2ttp.html