c语言迷宫问题的求解(栈和递归)

用C语言解决迷宫设计与寻找通路的问题摘要本课程设计主要解决设计一个迷宫以及在给出一组入口和出口的情况下，求出一条通路的问题。

在课程设计中，系统开发平台为Windows 2000，程序设计语言采用Visual C++6.0，数据结构采用链式栈存储结构，程序运行平台为Windows 98/2000/XP。

对于迷宫设计问题，首先假设了用“0”表示此道路可通，“1”表示不可通，即障碍，然后采用了简单的以时间产生随机种子（0，1变量）和人工输入0-1变量的方法产生迷宫矩阵。

对求解迷宫通路问题，采用“穷举求解”的方法和设计一个“先进后出”的栈来存放当前位置路径，最后得出一条动态行走迷宫的通路。

在程序设计中，采用了结构化与面向对象两种解决问题的方法。

程序通过调试运行，初步实现了设计目标。

关键词程序设计；C++6.0；链式栈存储结构；0-1；穷举求解1 引言本课程设计主要解决设计一个迷宫以及在给出入口和出口的情况下求解一条通路的问题。

利用“穷举求解”的方法来判定当前位置是否可通以及利用栈“先进后出”的特点来存放当前位置可通的信息。

1.1课程设计目的在我们对一个具体的问题进行分析时，往往要抽象出一个模型，设计一个算法来实现所需要达到的功能。

在此程序中，我们主要是综合运用所学过的知识，回顾VC++编程的同时，熟悉并掌握数据结构中的算法分析与设计。

同时，要掌握类C语言的算法转换成C程序并上机调试的基础；通过本次课程设计，进一步巩固《C语言》和《数据结构》课程所学的知识，特别是加强数据结构的理解与运用，熟悉面向对象的程序设计方法；通过此次课程设计的实践，锻炼自身程序设计的能力以及用C语言解决实际问题的能力，为以后后续课程的学习以及走上社会打好基础。

1.2课程设计内容根据对题目的分析和设想，首先，设计一个链式栈存储结构，动态的对迷宫数据进行操作（主要为入栈和出栈）；其次，定义一个二维数组和一个备份数组，用于存放迷宫数据，并在构建迷宫中，要完成对手动建立迷宫和自动建立迷宫方法的设计，并能输出原始迷宫信息和原始图形信息；再次，当程序接受外部输入一组入口、出口数据后，能完成对该迷宫矩阵计算出是否存在通路的情况，若存在通路，则分别用坐标通路和图形通路输出该通路，否则输出无通路的信息；最后，设计完成实现多次输入入口和出口数据后，计算出不同结果的情况，并能分别显示出对应信息。

⽤C语⾔解决迷宫问题#include <stdio.h>#include <stdlib.h>#define ROW 10#define COL 10/*迷宫中位置信息*/typedef struct position{int x;int y;}position;/*在迷宫中的当前位置的信息，也是⼊栈的基本元素*/typedef struct SElem{int di;position seat;}SElem;/*链式栈中节点的定义*/typedef struct position_stack{SElem p;struct position_stack *next;}*Stack_pNode,Stack_Node;void InitStack(Stack_pNode *Link){*Link = NULL;}void push(Stack_pNode *Link,SElem e){Stack_pNode new_SElem = (Stack_pNode)calloc(1,sizeof(Stack_Node));new_SElem->p = e;new_SElem->next = NULL;if (*Link == NULL)*Link = new_SElem;else{new_SElem->next = *Link;*Link = new_SElem;}}int pop(Stack_pNode *Link,SElem *e){if (*Link == NULL)return 0;*e = (*Link)->p;Stack_pNode q = *Link;*Link = (*Link)->next;free(q);return 1;}int top(Stack_pNode Link, SElem *e){if (Link == NULL)return 0;*e = Link->p;return 1;}int empty(Stack_pNode Link){if (Link == NULL)return 1;elsereturn 0;}int reverse(Stack_pNode *Link){Stack_pNode p, q, r;if (*Link == NULL || (*Link)->next == NULL)return 0;r = *Link;p = (*Link)->next;q = NULL;while (p){r->next = q;q = r;r = p;p = p->next;}r->next = q;*Link = r;}void print(Stack_pNode Link){Stack_pNode r = Link;while (r){printf("(%d,%d) -> ",r->p.seat.x,r->p.seat.y);r = r->next;}printf("exit\n");}int curstep = 1;/*纪录当前的⾜迹，填写在探索前进的每⼀步正确的路上*//*迷宫地图。

C语⾔递归实现迷宫寻路问题迷宫问题采⽤递归和⾮递归两种⽅法，暂时完成递归⽅法，后续会补上⾮递归⽅法#include<stdio.h>#include<stdbool.h>bool findPath(int a[][8],int i,int j){//递归找出⼝if(i==6&&j==6)//如果找到了⽬标a[6][6]则返回truereturn true;if(a[i][j]==0)//若当前路径未被找到，则继续{a[i][j]=2;//当前⾛的路径置为2，表⽰⾛过if(findPath(a,i+1,j)||findPath(a,i,j+1)||findPath(a,i-1, j)||findPath(a,i-1,j))//每个⽅向都判断，依次展开递归，寻找最佳路径return true;//若选择的路径可以⾛，则返回trueelse{//若当前选择的路径不能⾛a[i][j]=0;//弹栈并恢复路径，回退到上⼀次的位置return false;}}else//未能找到最终点return false;}void print(int a[][8])//打印当前的⼆维数组表{for(int i=0;i<8;i++){for(int j=0;j<8;j++){printf("%d ",a[i][j]);}printf("\n");}}int main(){int a[8][8]={0};for(int i=0;i<8;i++)//设置围墙和障碍物{a[0][i]=1;a[i][0]=1;a[7][i]=1;a[i][7]=1;}a[3][1]=1;a[3][2]=1;print(a);printf("-----------after find path-----------\n");findPath(a, 1, 1);print(a);}。

C语⾔实验：迷宫问题（搜索，C语⾔实现栈、队列）Description给定迷宫起点和终点，寻找⼀条从起点到终点的路径。

(0,1)(2,0)起点(1,1)(1,2)(1,3)(1,4)(2,0)(2,1)(2,4)(3,0)(3,1)(3,2)终点（3,4）(4,1)上图中黄⾊代表墙，⽩⾊代表通路，起点为(1,1)，终点为(3,4)。

要求搜寻策略是从起点开始按照“上、下、左、右”四个⽅向寻找终点，到下⼀个点继续按照“上、下、左、右”四个⽅⾯寻找，当该结点四个⽅向都搜寻完，但还没到终点时，退回到上⼀个点，直到找到终点或者没有路径。

⽐如上图从(1,1)开始，向上(0,1)不通，向下到(2,1)；到了(2,1)后继续按“上、下、左、右”四个⽅⾯寻找，上已经⾛过，向下到(3,1)；到(3,1)后上已经⾛过，下和左不通，向右到(3,2)；到(3,2)四个⽅⾯都不通，回到(3,1)四个⽅向都不通，再回到(2,1),(1,1)；到达(1,1)后下已经⾛过，左不通，继续向右⾛，重复这个过程最后到达(3,4)。

Input第⼀⾏两个数m和n表⽰迷宫的⾏数和列数。

迷宫⼤⼩不超过100×100第⼆⾏四个数x1,y1,x2,y2分别表⽰起点和终点的坐标。

接下来是m⾏n列的数，⽤来表⽰迷宫，1表⽰墙，0表⽰通路。

Output从起点到终点所经过的路径的坐标。

如果不存在这样的路径则输出“No Path!”。

Sample Input5 61 1 3 41 1 1 1 1 11 0 0 0 0 11 0 1 1 0 11 0 0 1 0 11 1 1 1 1 1Sample Output(1 1)(1 2)(1 3)(1 4)(2 4)(3 4)1.思路：（1）若当前点是终点，dfs函数返回1；（2）若不是终点，将此点标记为1，对该点4个⽅向进⾏搜索，实现⽅式为定义int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 通过⼀个⼩循环： for(int i = 0; i < 4; i++) {　 position nextp; nextp.x = dir[i][0] + now.x;nextp.y = dir[i][1] + now.y;...... }　进⾏搜索；若该点的下⼀个点nextp不是墙，未⾛，并且没有超界则将nextp压⼊栈中，递归调⽤dfs，若此过程经过（1）判断返回了1，说明最终找到了通往终点的路，便可以返回1，结束函数，此时栈中已储存了通往终点的路径，若没有通路，则弹出栈顶元素，根据递归原理该路径上的所有点都会弹出并标记未⾛，回溯到之前的点，继续向其他⽅向搜索，直到找到终点或遍历完整个图。

求迷宫问题就是求出从入口到出口的路径。

在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

首先用如图3.3所示的方块图表示迷宫。

对于图中的每个方块,用空白表示通道,用阴影表示墙。

所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下:int mg[M+1][N+1]={ /*M=10,N=10*/{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},/ 1{1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码：c语言描述如下：6/ 2void 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) /*找到了出口,输出路径*/ {瀠楲瑮?迷宫路径如下:\n);for (k=0;k<=top;k++){printf(\ (%d,%d),Stack[k].i,Stack[k].j); if ((k+1)%5==0) printf(\);}6/ 3printf(\);return;}find=0;while (di<4 && find==0) /*找下一个可走方块*/ { di++;switch(di){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;}6/ 4if (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--;}}牰湩晴尨没有可走路径!\n);}6/ 5（范文素材和资料部分来自网络，供参考。

求迷宫问题就是求出从入口到出口的路径。

在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

首先用如图所示的方块图表示迷宫。

对于图中的每个方块,用空白表示通道,用阴影表示墙。

所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下:int mg[M+1][N+1]={ /*M=10,N=10*/{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码：c语言描述如下：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("迷宫路径如下:\n");for (k=0;k<=top;k++){printf("\t(%d,%d)",Stack[k].i,Stack[ k].j);if ((k+1)%5==0) printf("\n");}printf("\n");return;}find=0;while (di<4 && find==0) /*找下一个可走方块*/{ di++;switch(di){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");}。

栈和队列的应⽤——迷宫问题（深度、⼴度优先搜索）⼀、迷宫问题 给⼀个⼆维列表，表⽰迷宫（0表⽰通道，1表⽰围墙）。

给出算法，求⼀条⾛出迷宫的路径。

maze = [[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1]] 1代表墙，0代表路，图⽰如下：⼆、栈——深度优先搜索 应⽤栈解决迷宫问题，叫做深度优先搜索（⼀条路⾛到⿊），也叫做回溯法。

1、⽤栈解决的思路 思路：从上⼀个节点开始，任意找下⼀个能⾛的点，当找不到能⾛的点时，退回上⼀个点寻找是否有其他⽅向的点。

使⽤栈存储当前路径。

后进先出，⽅便回退到上⼀个点。

2、⽤栈代码实现maze = [[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1]]# 四个移动⽅向dirs = [lambda x,y: (x+1, y), # 下lambda x,y: (x-1, y), # 上lambda x,y: (x, y-1), # 左lambda x,y: (x, y+1) # 右]def maze_path(x1, y1, x2, y2): # (x1,y1)代表起点；(x2,y2)代表终点stack = []stack.append((x1, y1))while(len(stack)>0):curNode = stack[-1] # 当前的节点(栈顶)if curNode[0] ==x2 and curNode[1] == y2: # 判断是否⾛到终点# ⾛到终点，遍历栈输出路线for p in stack:print(p)return True"""搜索四个⽅向"""for dir in dirs:nextNode = dir(curNode[0], curNode[1])# 如果下⼀个阶段能⾛if maze[nextNode[0]][nextNode[1]] == 0:stack.append(nextNode) # 将节点加⼊栈maze[nextNode[0]][nextNode[1]] = 2 # 将⾛过的这个节点标记为2表⽰已经⾛过了break # 找到⼀个能⾛的点就不再遍历四个⽅向else:# ⼀个都找不到，将该位置标记并该回退maze[nextNode[0]][nextNode[1]] = 2stack.pop()else:print("没有路")return Falsemaze_path(1,1,8,8)"""(1, 1) (2, 1) (3, 1) (4, 1) (5, 1) (5, 2) (5, 3) (6, 3) (6, 4)(6, 5) (7, 5) (8, 5) (8, 6) (8, 7) (8, 8)""" 总结算法就是：创建⼀个空栈，⾸先将⼊⼝位置进栈。

数据结构之迷宫问题求解（⼀）利⽤栈与递归求解出⼝ 本⽂适合于对迷宫问题已有初步研究,或阅读代码能⼒较强的⼈. 因此,如果你对迷宫问题⼀⽆所知,请参考其他更详细的资料. 迷宫问题,是⼀个对栈(Stack)典型应⽤的例⼦之⼀. 假如,有如下10X10的迷宫(0代表通路,1代表障碍),我们需要⽤写程序来找出迷宫的出⼝.1 1 1 1 1 1 1 1 1 11 1 1 0 1 1 1 0 1 10 0 0 0 1 0 0 0 1 11 1 0 1 1 0 1 0 0 11 1 0 1 0 0 1 0 1 11 1 0 1 1 1 1 0 0 11 1 0 0 0 0 0 0 1 11 1 0 1 0 1 1 0 1 11 1 0 1 0 1 1 0 1 11 1 1 1 1 1 1 0 1 1那么,我们可以通过两种⽅式完成.⽅式⼀:通过利⽤栈FILO(First In Last Out)的特性核⼼代码/**函数说明:通过栈来进⾏迷宫求解*参数说明:* Maze:迷宫地图数组* sz:迷宫⼤⼩* entry:迷宫⼊⼝点* path:⽤于寻找迷宫出⼝的栈*返回值:找到出⼝返回true,没找到返回false.*/bool FindMazePath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path){//将⼊⼝压栈path.push(entry);//如果栈不为空while(!path.empty()){//获取栈顶元素,即上⼀次⾛的路径Pos cur = path.top();//将其标记为已⾛过Maze[cur.x*sz+cur.y] = 3;//找到出⼝if(sz-1==cur.x){return true;}Pos next = cur;//下⼀步,向右移动next.x += 1;if(CheckIsAccess(Maze,sz,next)){//可以向右移动,将当前步⼊栈path.push(next);continue;}next = cur;//下⼀步,向左移动next.x -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向左移动,⼊栈path.push(next);continue;}//下⼀步,向上移动next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){//可以向上移动path.push(next);continue;}next = cur;//向下移动next.y -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向下移动path.push(next);continue;}//上、下、左、右都不能⾛path.pop();}return false;}⽅式⼆:通过递归核⼼代码/**函数说明:根据递归寻找迷宫出⼝*参数说明* Maze:迷宫地图* sz:迷宫⼤⼩* entry:迷宫⼊⼝* path:⽤来判断是否存在出⼝的栈*返回值:⽆(如果存在出⼝,栈为空;如果不存在出⼝,栈中存在起点坐标)*/void FindMazePathR(int *Maze,size_t sz,Pos &entry,stack<Pos> & path){//将⼊⼝压栈path.push(entry);Pos cur = entry;//将已⾛过的路标记为3Maze[cur.x*sz+cur.y] = 3;//找到出⼝,直接返回if(sz-1==entry.x){//将起点坐标弹出path.pop();return ;}Pos next = cur;//右next.x += 1;if(CheckIsAccess(Maze,sz,next)){//以当前位置为起点,递归进⾏下⼀步FindMazePathR(Maze,sz,next,path);}next = cur;//左next.x -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//上next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//下next = cur;next.y -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}path.pop();}最后,附上整个程序的完整代码(代码量较少,声明与实现我就不分⽂件了)迷宫问题求解完整代码//相关函数的声明与实现#ifndef __MAZE_H__#define __MAZE_H__#include<iostream>#include<iomanip>#include<stack>#include<assert.h>namespace Maze{using namespace std;//迷宫⼤⼩static const int N = 10;//迷宫地图⽂件名static const char *const FILENAME = "MazeMap.txt";//坐标struct Pos{int x; //横坐标(本质是数组arr[i][j]的j)int y; //纵坐标(本质是数组arr[i][j]的i)};/*函数说明:从⽂件中获取迷宫地图参数说明:Maze:迷宫地图数组sz:迷宫⼤⼩返回值:⽆*/void GetMaze(int *Maze,size_t sz){FILE *fp = fopen(FILENAME,"r");//打开失败if(NULL==fp){//输出错误信息perror(FILENAME);//结束程序exit(1);}//将⽂件中的迷宫地图读⼊Maze数组内for(size_t i=0; i<sz; ++i){for(size_t j=0; j<sz;){//从⽂件流中获取字符char tmp = getc(fp);//字符为0或为1时,导⼊数组if(tmp=='0'||tmp=='1'){Maze[i*sz+j]=tmp -'0';++j;}else if(EOF==tmp){//⽂件已读完,循环还未停⽌//说明此处⽂件中的迷宫地图存在问题assert(false);return ;}}}//关闭⽂件fclose(fp);}/*函数说明:打印迷宫参数说明:Maze:迷宫地图数组sz:迷宫⼤⼩返回值:⽆*/void PrintMaze(int *Maze,size_t sz){cout<<setw(2);for(size_t i=0; i<sz; ++i){for(size_t j=0; j<sz; ++j){cout<<Maze[i*sz+j]<<setw(2);}cout<<endl;}}/*函数说明:检测当前位置是否可以通过参数说明:Maze:迷宫地图数组sz:迷宫⼤⼩cur:当前所在位置返回值:可以通过返回true,不能通过返回false.*/bool CheckIsAccess(int *Maze,size_t sz,Pos cur){if(cur.x>=0 && cur.x<sz && //⾏坐标是否越界cur.y>=0 && cur.y<sz && //列坐标是否越界Maze[cur.x*sz+cur.y]==0 ){ //所在⾏列是否可以通过return true;}return false;}/*函数说明:通过栈来进⾏迷宫求解参数说明:Maze:迷宫地图数组sz:迷宫⼤⼩entry:迷宫⼊⼝点path:⽤于寻找迷宫出⼝的栈返回值:找到出⼝返回true,没找到返回false.*/bool FindMazePath(int *Maze,size_t sz,Pos &entry,stack<Pos>& path){ //将⼊⼝压栈path.push(entry);//如果栈不为空while(!path.empty()){//获取栈顶元素,即上⼀次⾛的路径Pos cur = path.top();//将其标记为已⾛过Maze[cur.x*sz+cur.y] = 3;//找到出⼝if(sz-1==cur.x){return true;}Pos next = cur;//下⼀步,向右移动next.x += 1;if(CheckIsAccess(Maze,sz,next)){//可以向右移动,将当前步⼊栈path.push(next);continue;}next = cur;//下⼀步,向左移动next.x -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向左移动,⼊栈path.push(next);continue;}//下⼀步,向上移动next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){//可以向上移动path.push(next);continue;}next = cur;//向下移动next.y -= 1;if(CheckIsAccess(Maze,sz,next)){//可以向下移动path.push(next);continue;}//上、下、左、右都不能⾛path.pop();}return false;}/**函数说明:根据递归寻找迷宫出⼝*参数说明* Maze:迷宫地图* sz:迷宫⼤⼩* entry:迷宫⼊⼝* path:⽤来判断是否存在出⼝的栈*返回值:⽆(如果存在出⼝,栈为空;如果不存在出⼝,栈中存在起点坐标)*/void FindMazePathR(int *Maze,size_t sz,Pos &entry,stack<Pos> & path){ //将⼊⼝压栈path.push(entry);Pos cur = entry;//将已⾛过的路标记为3Maze[cur.x*sz+cur.y] = 3;//找到出⼝,直接返回if(sz-1==entry.x){//将起点坐标弹出path.pop();return ;}Pos next = cur;//右next.x += 1;if(CheckIsAccess(Maze,sz,next)){//以当前位置为起点,递归进⾏下⼀步FindMazePathR(Maze,sz,next,path);}next = cur;//左next.x -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//上next = cur;next.y += 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}//下next = cur;next.y -= 1;if(CheckIsAccess(Maze,sz,next)){FindMazePathR(Maze,sz,next,path);}path.pop();}}#endif迷宫求解测试代码#include"Maze.h"using namespace Maze;void MazeTest(){int arr[N][N]; //迷宫地图Pos entry = {2,0}; //起点坐标stack<Pos> path; //栈GetMaze((int *)arr,N); //将⽂件中迷宫导⼊到arr数组中PrintMaze((int *)arr,N);//打印迷宫FindMazePath((int *)arr,N,entry,path);//找迷宫出⼝cout<<endl<<endl; //换⾏处理(使界⾯更整齐)PrintMaze((int *)arr,N);//打印⾛过的迷宫}int main(){MazeTest();return 0;}总结: 1.利⽤栈去寻找迷宫出⼝,栈内最终会保存从⼊⼝到出⼝的所有路径. 2.利⽤递归去寻找迷宫出⼝,传进去的栈仅仅只是⽤来判断迷宫是否有出⼝, 3.利⽤递归去寻找出⼝时,因为递归的特性,将会遍历完迷宫内的所有路径. 最后,还有⼀个问题:如果⼀个迷宫存在多条路径可以到达出⼝,那么如何得到迷宫到出⼝的最短路径 有机会的话,我将会在下篇⽂章讨论此事.。

c语言走迷宫代码以下是一个简单的 C 语言走迷宫代码示例，使用了递归算法: ```c#include <stdio.h>#include <stdlib.h>int main() {int size, row, col, choice, i, j;maze[0][0] = "*";maze[1][0] = "O";maze[0][1] = "O";maze[1][1] = "*";size = 2;row = 2;col = 2;while (1) {printf("Enter row: ");scanf("%d", &row);printf("Enter col: ");scanf("%d", &col);if (row < 0 || row > size || col < 0 || col > size) { printf("Invalid row or col. Try again.");}if (maze[row][col] != "*") {printf("Current cell is free. Try again. ");continue;}maze[row][col] = "X";printf("Enter a choice (1-6): ");scanf("%d", &choice);switch (choice) {case 1:row++;col = 0;break;case 2:row--;col = 0;break;case 3:col++;break;col--;break;case 5:row--;col = 1;break;case 6:row++;col = 1;break;default:printf("Invalid choice. Try again. ");continue;}}printf(" maze: ");for (i = 0; i < size * size; i++) { for (j = 0; j < size; j++) {if (maze[i][j] == "*")printf("*");elseprintf("%c", maze[i][j]);}printf("");}return 0;}```该程序首先初始化了一个 2x2 的迷宫，其中 `maze[0][0]` 和`maze[1][0]` 分别标记为 `"O"` 和 `"*"`,其他地方都为空。

数据结构与算法实验报告基于栈的C语言迷宫问题与实现一．问题描述多年以来，迷宫问题一直是令人感兴趣的题目。

实验心理学家训练老鼠在迷宫中寻找食物。

许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。

于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。

迷宫只有两个门，一个叫做入口，另一个叫做出口。

把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。

迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。

求解迷宫问题，即找出从入口到出口的路径。

一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。

现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。

下图是一个迷宫的示意图：迷宫示意图二．算法基本思想迷宫求解问题是栈的一个典型应用。

基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。

要实现上述算法，需要用到栈的思想。

栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。

如此反复循环，直到程序结束。

此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。

三．程序具体部分的说明1.迷宫的生成根据题目的要求，迷宫的大小是自定义输入的。

所以在程序中用malloc申请动态二维数组。

数组中的元素为随机生成的0、1。

数组周围一圈的元素全部定义为1，以表示边界。

数据结构C语言版_递归求解迷宫问题/*数据结构C语言版递归求解迷宫问题用递归函数求解迷宫问题(求出所有解)编译环境：Dev-C++ 4.9.9.2日期：2011年2月12日*/#include&lt;stdio.h&gt;// 迷宫坐标位置类型struct PosType{int x; // 行值int y; // 列值};#define MAXLENGTH 25 // 设迷宫的最大行列为25typedef int MazeType[MAXLENGTH][MAXLENGTH]; // [行][列]// 全局变量struct PosType end; // 迷宫终点位置MazeType m; // 迷宫数组int x, y; // 迷宫行数，列数// 定义墙元素值为0,可通过路径为-1,通过路径为足迹// 输出解void Print(int x,int y){int i,j;for(i=0;i&lt;x;i++){for(j=0;j&lt;y;j++)printf(&quot;%3d&quot;,m[i][j]);printf(&quot;\n&quot;);}printf(&quot;\n&quot;);}// 由当前位置cur、当前步骤curstep试探下一点void Try(struct PosType cur,int curstep){int i;struct PosType next; // 下一个位置// {行增量,列增量}struct PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// 移动方向,依次为东南西北for(i=0;i&lt;=3;i++) // 依次试探东南西北四个方向{next.x=cur.x+direc[i].x;next.y=cur.y+direc[i].y;if(m[next.x][next.y] == -1) // 是通路{m[next.x][next.y]=++curstep;if(next.x != end.x || next.y != end.y) // 没到终点Try(next,curstep); // 试探下一点(递归调用)elsePrint(x,y); // 输出结果m[next.x][next.y]=-1; // 恢复为通路，试探下一条路curstep--;}}}// 0为墙，-1为通道int main(){struct PosType begin; //起点int i,j,x1,y1;printf(&quot;请输入迷宫的行数,列数(包括外墙)：（空格隔开）&quot;); scanf(&quot;%d%d&quot;,&amp;x,&amp;y);for(i=0;i&lt;x;i++) // 定义周边值为0(同墙){m[0][i]=0; // 迷宫上面行的周边即上边墙m[x-1][i]=0;// 迷宫下面行的周边即下边墙}for(j=1;j&lt;y-1;j++){m[j][0]=0; // 迷宫左边列的周边即左边墙m[j][y-1]=0;// 迷宫右边列的周边即右边墙}for(i=1;i&lt;x-1;i++)for(j=1;j&lt;y-1;j++)m[i][j]=-1; // 定义通道初值为-1printf(&quot;请输入迷宫内墙单元数(即墙的个数)：&quot;);scanf(&quot;%d&quot;,&amp;j);if(j)printf(&quot;请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）\n&quot;); for(i=1;i&lt;=j;i++){scanf(&quot;%d%d&quot;,&amp;x1,&amp;y1);m[x1][y1]=0;}printf(&quot;迷宫结构如下:\n&quot;);Print(x,y);printf(&quot;请输入起点的行数,列数：（空格隔开）&quot;);scanf(&quot;%d%d&quot;,&amp;begin.x,&amp;begin.y);printf(&quot;请输入终点的行数,列数：（空格隔开）&quot;);scanf(&quot;%d%d&quot;,&amp;end.x,&amp;end.y);m[begin.x][begin.y]=1;Try(begin,1); // 由第一步起点试探起system(&quot;pause&quot;);return 0;}/*输出效果：请输入迷宫的行数,列数(包括外墙)：（空格隔开）4 4请输入迷宫内墙单元数(即墙的个数)：1请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）1 2迷宫结构如下:0 00 00 -1 0 00 -1 -1 00 0 0 0请输入起点的行数,列数：（空格隔开）1 1 请输入终点的行数,列数：（空格隔开）2 2 0 0 0 00 1 0 00 2 3 00 0 0 0请按任意键继续. . .*/。

顺序栈和迷宫求解（C语⾔）顺序栈 根据《数据结构》书中的讲解，对顺序栈的⼀个基本实现。

define.h1// define.h2 #ifndef __MENGQL_DEFINE__3#define __MENGQL_DEFINE__45#define C_LOG_DBG(format, ...)6//printf("[%s@%s,%d] " format ,__FUNCTION__, __FILE__, __LINE__, ##__VA_ARGS__);7#define C_LOG_ERR(format, ...) printf("[%s@%s,%d] " format ,__FUNCTION__, __FILE__, __LINE__, ##__VA_ARGS__);8 typedef enum EStatus {ERROR, OK} Status;910#endifSqStack.h1// SqStack.h2 #ifndef __SQ_STACK_H__3#define __SQ_STACK_H__4 #include "define.h"56 typedef struct7 {8int x;9int y;10 }PosType;1112 typedef struct13 {14int ord;15 PosType seat;16int di;17 }SElemType;1819#define STACK_INIT_SIZE 10020 typedef struct21 {22 SElemType* base;23 SElemType* top;24int stacksize;25 }SqStack;2627extern Status InitStack(SqStack *S);28extern Status GetTopStack(SqStack S, SElemType *e);29extern Status PushStack(SqStack *S, SElemType e);30extern Status PopStack(SqStack *S, SElemType *e);31extern Status StackEmpty(SqStack *S);32extern Status DestoryStack(SqStack *S);33#endifSqStack.c1// SqStack.c2 #include "define.h"3 #include "SqStack.h"4 #include <stdlib.h>5 #include <stdio.h>6 Status InitStack(SqStack *S)7 {8 S->stacksize = STACK_INIT_SIZE;9 S->base = (SElemType *)malloc(S->stacksize * sizeof(SElemType));10if(S->base == NULL)11 {12 C_LOG_ERR("%s\n","MALLOC OVERFLOW");13return ERROR;14 }15 S->top = S->base;1617return OK;18 }19 Status GetTopStack(SqStack S, SElemType *e)20 {21if(S.top == S.base)22 {23 C_LOG_ERR("%s\n","STACK IS EMPTY");24return ERROR;25 }26 *e = *(S.top-1);27return OK;28 }29 Status PushStack(SqStack *S, SElemType e)30 {31if(S->top - S->base >= S->stacksize)32 {33 S->base = (SElemType *)realloc(S->base, (S->stacksize * 2) * sizeof(SElemType)); 34if(S->base == NULL)35 {36 C_LOG_ERR("%s\n","REMALLOC OVERFLOW");37return ERROR;38 }39 S->stacksize *= 2;40 }41 *(S->top++) = e;42return OK;43 }44 Status PopStack(SqStack *S, SElemType *e)45 {46if(S->top == S->base)47 {48 C_LOG_ERR("%s\n","STACK IS EMPTY");49return ERROR;50 }51 *e = *(--S->top);52return OK;53 }54 Status StackEmpty(SqStack *S)55 {56if(S->top == S->base)57 {58return OK;59 }60return ERROR;61 }62 Status DestoryStack(SqStack *S)63 {64 S->stacksize = 0;65 free(S->base);66 S->top = S->base = NULL;67return OK;68 }迷宫求解 顺序栈实现的迷宫求解是深度优先搜索，得出的路径是⾮最短路径。

应⽤栈解决迷宫问题的C语⾔实现题⽬来⾃于严蔚敏《数据结构》，参考伪代码实现的程序：1 #include <stdio.h>2 #include <malloc.h>3//记录通道块在迷宫矩阵当中的横、纵坐标4struct Position{5int x;6int y;7 };8//放⼊栈当中的通道块元素9struct SElement {10int ord;//记录此通道块在整个通道当中的次序11 Position p;//记录此通道块在矩阵当中的位置12int di;//记录下⼀次测试这⼀路径的临近路径的位置13 };14//创建栈数据结构15#define STACK_INIT_SIZE 10016#define STACKINCREMENT 1017struct MyStack{18 SElement* base;19 SElement* top;20int stacksize;21 };22//创建⼀个栈如果创建成功则返回1，否则就返回023int InitStack(MyStack* s)24 {25 s->base=(SElement*)malloc(STACK_INIT_SIZE*sizeof(SElement));//为栈分配初始空间26if(!s->base) return0;27 s->top=s->base;//设定为空栈28 s->stacksize=STACK_INIT_SIZE;29return1;30 }31//判断栈是否为空，如果是空的就返回0，否则就返回132int IsStackEmpty(MyStack* s)33 {34if(s->top==s->base) return true;35return false;36 }37//获取栈顶元素,如果栈为空就返回0 否则就返回138int GetTop(MyStack* s,SElement* e)39 {40if(IsStackEmpty(s)) return0;41 e=s->top-1;42return1;43 }44//获取栈的长度，并且通过程序返回45int StackLength(MyStack* s)46 {47return s->top-s->base;48 }49//插⼊元素e为新的栈顶元素，插⼊成功则返回1，否则返回050int Push(MyStack* s,SElement e)51 {52if(s->top-s->base>=STACK_INIT_SIZE)53 {54 s->base=(SElement*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElement));55if(!s->base) return0;56 s->top=s->base+s->stacksize;57 s->stacksize+=STACKINCREMENT;58 }59 *(s->top)=e;60 s->top++;61return1;62 }63//弹出栈顶元素赋值给e弹出成功返回1，弹出失败返回064int Pop(MyStack* s,SElement* e)65 {66if(IsStackEmpty(s)) return0;67 *e=*(s->top-1);68 s->top--;69return1;70 }71//定义墙元素为2 可⾛路径为0 已知路径为curStep 不能够通过的路径为-172#define MazeScale 1073int Maze[MazeScale][MazeScale]={{2,2,2,2,2,2,2,2,2,2},{2,0,0,2,0,0,0,2,0,2},{2,0,0,2,0,0,0,2,0,2},{2,0,0,0,0,2,2,0,0,2},74 {2,0,2,2,2,0,0,0,0,2},{2,0,0,0,2,0,0,0,0,2},{2,0,2,0,0,0,2,0,0,2},{2,0,2,2,2,0,2,2,0,2},{2,2,0,0,0,0,0,0,0,2},{2,2,2,2,2,2,2,2,2,2}}; 75//辅助函数考察当前路径能否通过76bool Pass(Position posi)77 {78//只有路径所在位置的数字为0的是可以⾛的79if(Maze[posi.x][posi.y]==0)80 {81return true;82 }83return false;84 }85//按顺时针⽅向从东开始寻找矩阵当中某⼀个位置的临近位置86 Position NextPosition(Position now,int direction)87 {88 Position next;89int x=now.x;90int y=now.y;91switch(direction)92 {93//东94case1:{95 next.x=x;96 next.y=y+1;97break;98 }99//南100case2:{101 next.x=x+1;102 next.y=y;103break;104 }105//西106case3:{107 next.x=x;108 next.y=y-1;109break;110 }111//北112case4:113 {114 next.x=x-1;115 next.y=y;116break;117 }118default:break;119 }120return next;121 }122//留下⾜迹123void FootPrint(Position p,int step)124 {125 Maze[p.x][p.y]=step;126 }127//路径不可⾛的话就留下-1的标记128void MarkPrint(Position p)129 {130 Maze[p.x][p.y]=-1;131 }132int main()133 {134//打印出迷宫矩阵135for(int i=0;i<MazeScale;i++)136 {137for(int j=0;j<MazeScale;j++)138 {139 printf("%d ",Maze[i][j]);140 }141 printf("\n");142 }143//迷宫程序主体144 MyStack path;//记录路径的栈145 InitStack(&path);//初始化路径数组146 Position curp;//当前被试位置147//初始化当前位置为矩阵⼊⼝148 curp.x=1;149 curp.y=1;150int curStep=1;//被探索的步数151do152 {153if(Pass(curp))154 {155 FootPrint(curp,curStep);//可⾛就在迷宫⾥⾯留下⾜迹156//创建⼀个栈元素，存储可⾏路径的相关值，将这个元素存储到栈当中157 SElement e;158 e.di=1;//意味着下⼀个被试路块为这⼀个路块的正上⽅的路块159 e.ord=curStep;160 e.p.x=curp.x;161 e.p.y=curp.y;162 Push(&path,e);//将路径块⼊栈163if(curp.x==MazeScale-2 && curp.y==MazeScale-2) break; //如果被压⼊的路径块到了迷宫的终点就退出循环164//找到下⼀个被试块165 curp=NextPosition(curp,1);//找到前⼀个被试块东⾯的路径块作为被试块166 curStep++;//被探索的步数加⼀167 }else//如果当前被试路径不能够通过的话168 {169if(!IsStackEmpty(&path))170 {171 SElement e;172 Pop(&path,&e);173 curStep--;174//将这⼀段所有的周围路径都已经被测试过的路径从栈中清除175while(e.di==4 && !IsStackEmpty(&path)){176 MarkPrint(e.p);177 Pop(&path,&e);178 curStep--;179 }180//如果当前栈顶还有未被测试的路径就测试剩余的周围路径181if(e.di<4)182 {183 curp=NextPosition(e.p,e.di+1);184 e.di++;185 curStep++;186 Push(&path,e);187 }188 }189 }190 }while(!IsStackEmpty(&path));191 printf("\n");192//打印出结果迷宫矩阵193for(int i=0;i<MazeScale;i++)194 {195for(int j=0;j<MazeScale;j++)196 {197 printf("%d ",Maze[i][j]);198 }199 printf("\n");200 }201return0;202 }。

数据结构试验——迷宫问题（一）基本问题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设计运算算法要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。

在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。

后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。

用栈求解迷宫问题所有路径及最短路径程序c语言
摘要：
1.迷宫问题的背景和意义
2.栈的基本概念和原理
3.用栈解决迷宫问题的方法
4.C 语言编程实现步骤
5.程序示例及运行结果
正文：
【1.迷宫问题的背景和意义】
迷宫问题是计算机科学中的一个经典问题，它涉及到图论、数据结构和算法等多个领域。

在迷宫问题中，给定一个有向图，目标是找到从起点到终点的所有路径以及最短路径。

这个问题在现实生活中也有很多应用，例如地图导航、物流路径规划等。

【2.栈的基本概念和原理】
栈是一种线性数据结构，它遵循后进先出（LIFO）的原则。

栈可以用来存储序列中的元素，也可以用来表示函数调用关系。

栈的操作通常包括入栈、出栈、获取栈顶元素等。

【3.用栈解决迷宫问题的方法】
为了解决迷宫问题，我们可以使用栈来记录遍历过程中的路径。

具体步骤如下：
1.创建一个栈，用于存储遍历过程中的路径；
2.从起点开始，将当前节点的编号入栈；
3.遍历当前节点的所有相邻节点，如果相邻节点未被访问过，则将其入栈；
4.当栈不为空时，继续执行步骤3；否则，说明已到达终点，开始回溯，找到最短路径；
5.从栈顶弹出节点，将其添加到结果路径列表中；
6.如果栈为空，说明没有找到从起点到终点的路径；否则，返回结果路径列表。

/*人民邮电大学——迷宫求解*/#include <stdio.h>#include <stdlib.h>#define MAX 100/* 栈中最大元素个数 */#define NLENGTH 11 /*地图的第一维长度*/typedef struct{int x;/* 行下标 */int y;/* 列下标 */int d;/* 运动方向 */}DataType;struct SeqStack{ /* 顺序栈类型定义 */int t; /* 指示栈顶位置 */DataType s[MAX];};typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */ PSeqStack pastack;PSeqStack createEmptyStack_seq( void ){PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(struct SeqStack));if (pastack == NULL)printf("内存申请失败!! \n");elsepastack->t = -1;return pastack;}/*空栈吗？*/int isEmptyStack_seq( PSeqStack pastack ){return pastack->t == -1;}/*入栈操作：一个参数*/void Push_seq( PSeqStack pastack, DataType x ){if( pastack->t > MAX)printf( "堆栈溢出错误!\n" );else{pastack->t++;pastack->s[pastack->t] = x;}}/*出栈操作 */void Pop_seq( PSeqStack pastack ){if (pastack->t == -1 )printf( "堆栈溢出错误!\n" );elsepastack->t--;}/*取栈顶元素*/DataType Top_seq( PSeqStack pastack ){return (pastack->s[pastack->t]);}/*入栈操作：四个参数*/void Push_Stack(PSeqStack st, int x, int y, int d){DataType element;element.x = x;element.y = y;element.d = d;Push_seq(st, element);}/*输出路径*/void OutputPath(PSeqStack st){DataType element;printf("\n\n出迷宫的路径是:\n");while(!isEmptyStack_seq(st)){element = Top_seq(st);Pop_seq(st);printf("\n路过的节点坐标是: 第%d行第%d列 ", element.x, element.y); /* 打印路径上的每一点 */}}/*迷宫求解主函数*/void Maze_Path(int Maze[][NLENGTH], int direction[][2], int x1, int y1, int x2, int y2){int i, j, k, g, h;PSeqStack st;DataType element;st = createEmptyStack_seq( );Maze[x1][y1] = 2; /* 从入口开始进入,作标记 */Push_Stack(st, x1, y1, -1); /* 入口点进栈 */while ( !isEmptyStack_seq(st)){ /* 回退 */Pop_seq(st);element = Top_seq(st);if(isEmptyStack_seq(st)){element.x=x1;element.y=y1;element.d=-1;}i = element.x;j = element.y;for (k = element.d + 1; k <= 3; k++){ /* 依次试探每个方向 */g = i + direction[k][0];h = j + direction[k][1];if (g == x2 && h == y2 && Maze[g][h] == 0){ /* 走到出口点 */Push_Stack(st, x2, y2, -1); /* 出口点进栈 */OutputPath(st); /* 输出路径 */return;}if (Maze[g][h] == 0){ /*道路通畅，未免重复对走到没走过的点作标记 */Maze[g][h] = 2;Push_Stack(st, g, h, k); /* 进栈 */i = g; j = h; k = -1; /* 下一点转换成当前点 */}}}printf("\n未找到路径.\n");/* 栈退完未找到路径 */}/*迷宫数据*/int Maze[][11] ={1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1};int direction[][2]={0,1,/*x不变，Y+1*/1,0,/*X+1，Y不变*/0,-1,/*X不变，Y-1*/-1,0 /*X-1，Y不变*/}; /*向四面运动时，X，Y的增减量,即方向*/int main(){int x1,x2,y1,y2,i,j;/*入口，出口，循环变量声明*/x1 =1;y1 =1;x2 = 9;y2 = 9;for(i = 0;i<11;i++){for(j=0;j<11;j++){printf("%d ",Maze[i][j]);}printf("\n\r");}printf("从结点:第%d行,第%d列到达结点:第%d行,第%d列",x2,y2,x1,y1);Maze_Path(Maze,direction,x1,y1,x2,y2);return 0;}//QQ交流群248936001。