当前位置：文档之家 › 数据结构小组课题——迷宫

数据结构小组课题——迷宫

  • 格式：doc
  • 大小：104.50 KB
  • 文档页数：17

数据结构——迷宫求解迷宫问题最早出现在古希腊神话中。

据说，半人半兽的英雄西修斯在克里特的迷宫中勇敢地杀死半人半牛的怪物，并循着绳索逃出迷宫。

希腊史学家希罗多德曾探访过那里。

他描述说，整个迷宫由12座带顶院落构成，所有的院落都由通道连接，形成3000个独立的“室”。

后来的参观者也说，一旦进入迷宫，如果没有向导，根本无望走出。

历史上，人们认为迷宫具有魔力。

后来，迷宫成为游戏。

在如今计算机非常普及的情况下，迷宫又以游戏程序的形式呈现在我们日常使用的电脑上。

解题思路解析：在迷宫问题中，一个迷宫用二维数组maze[size] [size]来存储，对当前位置（探索过程中某一时刻所在的位置）记为maze[curpos.row][curpos.line]，如果maze[curpos.row][curpos.line]=0则有通路，如果maze[curpos.row][curpos.line]=1则无通路。

从入口star出发，可沿四个方向前进。

试探方向的变化0表示E、1表示S、2表示W、3表示N。

如果遇到“0”则可前进，遇“1”则受阻；按此规则求入口到某一确定出口的一条路径。

算法的基本思想是：从迷宫的入口出发，进行判断，若当前位置可通（未走过的“0”），则将当前位置插入栈顶，然后判断此位置是否为出口位置，如果是则结束整个运算，若不是出口位置，改变当前位置到他的右临位置（即E方向）；否则如果当前位置不通，这时若栈不空且栈顶位置尚有其他位置未搜索，则设定新的当前位置为栈顶位置的下一邻块，若栈不空且栈顶位置四周不通，则删去栈顶位置，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的邻块或栈空，如此重复判断，直到找到一条从入口到出口的一条路径或得到无路径的信息。

一.需求分析问题描述：以一个size*size的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。

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

a、输入的形式和输入值的范围：以0，1输入表示迷宫，0为通路，1为障碍。

向电脑输入由0和1组成的二维数组，数组的行号列号相同且都为size（1=<size<=10）。

b、输出的形式：首先输出迷宫“#”表示墙壁，“0”表示通道，“1”表示障碍。

然后输出走出迷宫的路径，“#”表示墙壁，“0”表示迷宫通路，由于时间仓促不免会有些瑕疵，当好多“0”紧挨在一起的时候，有顺时针方向表示迷宫通道（由右方开始）。

c、程序所能达到的功能：实现输出迷宫通道，当迷宫无通道时显示“找不到通路”。

d、测试数据：由后面调试分析详细说明。

二.概要设计1．数据结构的定义为实现输出迷宫路径需用到栈，下面定义栈的抽象数据类型：栈（stack）是限定仅在表尾进行插入或删除操作的线性表。

因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。

不含元素的空表称为空栈。

假设栈S=（a1,a2,…，an），则称a1为栈底元素，an为栈顶元素。

栈的修改是按后进先出的原则进行的。

因此，栈又称为后进先出（List In First Out）的线性表。

（简称LIFO结构）ADT Stack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n, n>=0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n,}约定an端为栈顶，a1端为栈底。

在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

由此，“纳入可以走的路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

2．程序模块(1)迷宫和栈的定义：typedef enum { ERROR, OK } Status;typedef struct{int row; //row表示“行”号int line; //line表示“列”号}PosType; //位置的元素类型typedef struct{int ord; //该通道在路径上的“序号”PosType seat; //通道块在迷宫中的“坐标位置”int di; //从此通道走向下以通道块的“方向”}SElemType; //栈的元素类型typedef struct{SElemType * base; //在构造之前和销毁之后，base的值为NULLSElemType * top; //栈顶指针int stacksize; //当前已分配的存储空间}SqStack;(2)构造一个空栈S：Status InitStack(SqStack &S){S.base=(SElemType *)malloc(100*sizeof(SElemType));if(!S.base)return ERROR; //存储分配失败S.top=S.base;S.stacksize=100;return OK;}(3)进栈：Status Push（SqStack &S，SElemType &e）{ //插入元素e为新的栈顶元素if (S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType*) realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof (ElemType));If(!S.base) exit (overflow) //存储分配失败S.top=S.base+S.stacksize;S.stacksize+= STACKINCREMENT;}*S.top++=e;Return OK;}由于本题中在为栈分配存储空间的时候S.stacksize=100，为迷宫最大的元素数，因此不存在栈满的情况。

(4)删除栈顶元素：Status Pop(SqStack &S,SElemType &a){ //若栈不空，则删除S的栈顶元素，用a返回其值，并返回OK，否则返回ERROR if(S.top==S.base)return ERROR;a=*--S.top;return OK;}(5)判栈空：Status StackEmpty(SqStack S){if(S.top==S.base) return OK;return ERROR;}3、各模块之间的调用关系:(1)本程序主要包括以下函数：(1)主函数main()(2)初始化迷宫函数Initmaze()(3)显示所创建的迷宫函数printmaze ()(4)进入下一个位置函数NextPos()(5)创建空栈函数InitStack()(6)检查是否为空栈函数StackEmpty()(7)插入栈元素函数push ()(8)删除栈元素函数pop ()(9) 寻找到路径函数mazepath ()(10) 输出路径函数printpath()(11)标记当前位置函数Markfoot()(12)判断当前位置是否可通函数Pass()（2）各种函数之间的调用关系如下：三.详细设计：解决迷宫问题最重要的程序段是找到通路，并存储在栈里，现只分析实现这一过程的函数MazePath()，其余调用函数在附录里有详细说明：do {若当前位置可通，则{ 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的右邻方块为新的当前位置；}否则，若栈不空且栈顶位置尚有其他方向未经探索，则设定的新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{ 删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；}}while（栈不空）；在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。

Status MazePath (MazeType maze,PosType start, PsoType end) {//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中(从栈底到//栈顶)，并返回TURE；否则返回FALSEInitStack(S); curpos=start; //设定“当前位置”位“入口位置”curstep=1; //探索第一步do{if (Pass(curpos)) { //当前位置可以通过，即是未曾走到过的通道块FootPrint(curpos); //留下足迹e=(curstep,curpos,1);Push(S,e); //加入路径if (curpos==end) return (TRUE); //到达终点(出口)curpos=NextPos(curpos,1); //下一位置是当前位置的右邻curstep++; //探索下一步}else { //ifif (!StackEmpty(S)) { //当前位置不能通过Pop (S,e);while (e.di==3 && !StackEmpty(S)) {MarkPrint(e.seat); Pop(S,e); //留下不能通过的标记，并退回一步}if (e.di<3) {e.di++; Push (S,e); //换下一个方向探索curpos=NextPos (e.seat e.di); //设定当前位置是该新方向上的相邻块} //if} //if} //else}while (!StackEmpty(S));return (FALSE);} //MazePath四.调试分析：a、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：遇到的问题：（1）首先是对实现迷宫由当前方向转向下一方向时应当怎样实现遇到了困难，具体解析见解题思路。

（2）然后是当前位置不可通，即当前位置的四周方向都试探过后发现不是通路，如何实现退向后一位置。

如果当前位置不通，则留下足迹即把当前位置标记为1，再把当前位置从栈顶位置删除，这样此位置就不会循环往复的再次被走到。

（3）如何实现输出迷宫通路的问题。

当当前位置坐标和迷宫终点坐标相同时，即迷宫走到出口。

这时迷宫里所有元素还是由“0”和“1”组成，把栈中元素标记为“2”以示和别的元素区别。

把数组中所有为“2”的元素输出“0”,不是2的元素输出“”，围墙由“#”输出。

这样就解决了迷宫路径的输出问题。

在这个问题上由于输入数据的时候是输入一个0或1，然后再输入一个空格，这样会比较美观。

但是最初想到的是用“”即一个空格代表不是通路的元素，这样最终输出的时候就出现问题了，迷宫的最右端围墙“#”会不在最后一列出现，输出错误的通道或者就显示不出通道。

合集下载

数据结构程序设计(迷宫问题)

数据结构程序设计(迷宫问题)

数据结构程序设计(迷宫问题)数据结构程序设计(迷宫问题)一、引言迷宫问题是计算机科学中常见的问题之一，它涉及到了数据结构的设计和算法的实现。

本文将介绍迷宫问题的定义、常见的解决算法和程序设计思路。

二、问题定义迷宫问题可以描述为：给定一个迷宫，迷宫由若干个连通的格子组成，其中有些格子是墙壁，有些格子是路径。

任务是找到一条从迷宫的起点（通常是左上角）到终点（通常是右下角）的路径。

三、基本数据结构1.迷宫表示：迷宫可以使用二维数组来表示，数组中的每个元素代表一个格子，可以用0表示路径，用1表示墙壁。

2.坐标表示：可以使用二维坐标表示迷宫中的每一个格子，使用(x, y)的形式表示。

四、算法设计1.深度优先搜索算法：深度优先搜索算法可以用来解决迷宫问题。

算法从起点开始，尝试向四个方向中的一个方向前进，如果可以移动则继续向前，直到到达终点或无法继续移动。

如果无法继续移动，则回溯到上一个节点，选择另一个方向继续搜索，直到找到一条路径或者所有路径都已经探索完毕。

2.广度优先搜索算法：广度优先搜索算法也可以用来解决迷宫问题。

算法从起点开始，先将起点加入队列，然后不断从队列中取出节点，并尝试向四个方向中的一个方向移动，将新的节点加入队列。

直到找到终点或者队列为空，如果队列为空则表示无法找到路径。

五、程序设计思路1.深度优先搜索算法实现思路：a) 使用递归函数来实现深度优先搜索算法，参数为当前节点的坐标和迷宫数据结构。

b) 判断当前节点是否为终点，如果是则返回成功。

c) 判断当前节点是否为墙壁或已访问过的节点，如果是则返回失败。

d) 将当前节点标记为已访问。

e) 递归调用四个方向，如果存在一条路径则返回成功。

f) 如果四个方向都无法找到路径，则将当前节点重新标记为未访问，并返回失败。

2.广度优先搜索算法实现思路：a) 使用队列保存待访问的节点。

b) 将起点加入队列，并标记为已访问。

c) 不断从队列中取出节点，尝试向四个方向移动，如果新的节点未被访问过且不是墙壁，则将新的节点加入队列，并标记为已访问。

数据结构(C语言版)实验报告(迷宫)

数据结构(C语言版)实验报告(迷宫)

《数据结构与算法》实验报告评分依据及结果一、需求分析1.问题描述：以一个m*n的长方阵表示迷宫，空格和感叹号分别表示迷宫中的通路和障碍。

设计一个程序，对随机产生的迷宫，求一条从入口到出口的通路，或得出没有通路的结论。

2.基本要求首先实现一个以链表为存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i，j，d）的形式输出。

其中（i，j）表示迷宫的一个坐标，d表示走到下一座标的方向。

3.程序的执行命令有：1）输入迷宫的列数2）输入迷宫的行数二、概要设计为实现上述功能，需要以一个链表为存储结构的栈类型1.栈的顺序存储表示typedef struct{int x; /*列*/int y; /*行*/}PosType; //坐标位置类型typedef struct{int ord; //通道块在路径上的"序号"PosType seat; //通道块在迷宫中的"坐标位置"int di; //从此通道块走向下一通道块的"方向"}SElemType; //栈的元素类型typedef struct{SElemType *base;SElemType *top;int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;//迷宫程序typedef struct{int lie; /*列数*/int hang; /*行数*/char a[999][999];}MazeType; /*迷宫类型*/2.基本操作int InitStack(SqStack *S)//分配空间int GetTop(SqStack *S,SElemType *e) //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint Push(SqStack *S,SElemType *e)//插入元素e作为新的栈顶元素int Pop(SqStack *S,SElemType *e) //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORint generatemaze( MazeType *maze)// 随机生成迷宫int Pass(MazeType *maze, PosType curpos ) //判断当前位置可否通过int FootPrint(MazeType *maze,PosType curpos) //留下足迹int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记PosType NextPos(PosType curpos,int di) //返回当前位置的下一位置int MazePath(MazeType *maze,PosType start,PosType end) //若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR void PrintMaze(MazeType *maze) //打印迷宫三、详细设计//程序的头文件#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>#include <time.h>//函数的返回值#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10//栈的顺序存储表示typedef struct{int x; /*列*/int y; /*行*/}PosType; //坐标位置类型typedef struct{int ord; //通道块在路径上的"序号"PosType seat; //通道块在迷宫中的"坐标位置"int di; //从此通道块走向下一通道块的"方向"}SElemType; //栈的元素类型typedef struct{SElemType *base;SElemType *top;int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;//基本操作int 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;}//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack *S,SElemType *e){if(S->top==S->base)return ERROR;*e=*(S->top-1);return OK;}int Push(SqStack *S,SElemType *e)//插入元素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;}//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORint Pop(SqStack *S,SElemType *e){if(S->top==S->base)return ERROR;*e=*--S->top;return OK;}int StackEmpty(SqStack *S){return(S->top==S->base);}//迷宫程序typedef struct{int lie; /*列数*/int hang; /*行数*/char a[999][999];}MazeType; /*迷宫类型*//*随机生成迷宫*/int generatemaze( MazeType *maze){int i,j;maze->a[0][0]=2;maze->a[++maze->hang][++maze->lie]=3; /*设置外墙*/maze->a[0][maze->lie]='!';maze->a[maze->hang][0]='!';for(j=1;j<maze->lie;j++){maze->a[0][j]='!';maze->a[maze->hang][j]='!';}for(i=1;i<maze->hang;i++){maze->a[i][0]='!';maze->a[i][maze->lie]='!';}srand((unsigned)time( NULL ));rand();for(i=1; i <maze->hang; i++)for(j=1;j<maze->lie;j++){if (rand()>=RAND_MAX/4) maze->a[i][j] =' '; //' ' 暗示出路else maze->a[i][j] ='!'; //'!'暗示无出路}return OK;}int Pass(MazeType *maze, PosType curpos ) //判断当前位置可否通过{if ((curpos.x < 1) || (curpos.x >= maze->lie))return ERROR;if ((curpos.y < 1) || (curpos.y >= maze->hang))return ERROR;if (maze->a[curpos.y][curpos.x]==' ')return OK;else return ERROR;}int FootPrint(MazeType *maze,PosType curpos) //留下足迹{maze->a[curpos.y][curpos.x]='*';return OK;}int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记{maze->a[curpos.y][curpos.x]='@';return OK;}PosType NextPos(PosType curpos,int di)//返回当前位置的下一位置{PosType pos=curpos;switch(di){case 1: //右东pos.x++;break;case 2: //下南pos.y++;break;case 3: //左西pos.x--;break;case 4: //上北pos.y--;break;}return pos;}//若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR int MazePath(MazeType *maze,PosType start,PosType end){PosType curpos;SqStack *S=(SqStack *)malloc(sizeof(SqStack));InitStack(S);SElemType *e;e=(SElemType *)malloc(sizeof(SElemType));curpos=start; //设定当前位置为入口位置int curstep = 1; //探索第一步do {if(Pass(maze,curpos)) //当前位置可通过{FootPrint(maze,curpos);e->ord=curstep;e->seat=curpos;e->di=1;Push(S,e);if(curpos.x==end.x&&curpos.y==end.y)return (OK);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);}if(e->di<4) //栈不空且栈顶位置四周有其他位置未探索{e->di++;Push(S,e);curpos=e->seat;curpos=NextPos(curpos,e->di);}}}}while(!StackEmpty(S));return ERROR;}void PrintMaze(MazeType *maze) //打印迷宫{int i,j,k,n;int c[999],d[999];for(i=0,k=0;i<=maze->hang;i++){for(j=0;j<=maze->lie;j++){printf("%c ",maze->a[i][j]);if(maze->a[i][j]=='*'){c[k]=i;d[k]=j;k++;}}printf("\n");}n=k;for(k=0;k<n;k++)printf("<%d,%d>",c[k],d[k]);printf("\n");printf("\n");}int main(){int zmg;char ch;printf(" 数据结构课程设计--迷宫问题求解\n\n");printf(" |----------------------------------------|\n");printf(" | |\n");printf(" | |\n");printf(" | |\n");printf(" | |\n");printf(" | XXXX XXXXXXXXXXXXXX |\n");printf(" | XXXXXXX |\n");printf(" |----------------------------------------|\n");getchar();do{system("cls");fflush(stdin);MazeType *maze=(MazeType *)malloc(sizeof(MazeType)); //设置迷宫的长宽不含外墙printf("请输入迷宫的列数（不含外墙时）:");scanf("%d",&maze->lie);printf("请输入迷宫的行数（不含外墙时）:");scanf("%d",&maze->hang);generatemaze(maze);printf("随机创建迷宫\n");PrintMaze(maze);getchar();getchar();PosType start,end;start.x=1;start.y=1;end.x=maze->lie-1;end.y=maze->hang-1;zmg=MazePath(maze,start,end);if(zmg){printf("此迷宫通路为\n");PrintMaze(maze);}elseprintf("此迷宫无通路\n"); //getchar();printf("再次尝试？（Y/N）?");scanf("%c",&ch);}while(ch=='Y'||ch=='y');return 0;}四、调试分析1.本程序界面设计合理，以空格为通路，感叹号！为障碍，笑脸为起始点，*为行走路线，心形为出口设计精巧，便于用户使用。

数据结构-迷宫实验报告

数据结构-迷宫实验报告

数据结构-迷宫实验报告数据结构-迷宫实验报告1.引言1.1 背景迷宫是一个有趣又具有挑战性的问题，它可以用于测试和评估不同的搜索算法和数据结构。

在这个实验报告中，我们将使用不同的数据结构和算法来解决迷宫问题。

1.2 目的本实验的目的是比较使用不同数据结构和算法解决迷宫问题的效率和性能。

我们将尝试使用栈、队列和递归等方法进行迷宫的搜索。

2.方法2.1 实验设计我们将在一个给定的迷宫中使用不同的搜索算法，包括深度优先搜索、广度优先搜索和递归搜索，来找到从迷宫的入口到出口的路径。

我们还将使用栈和队列数据结构来实现这些搜索算法。

2.2 实验步骤1) 定义迷宫的结构，并初始化迷宫的入口和出口。

2) 使用深度优先搜索算法找到迷宫中的路径。

3) 使用广度优先搜索算法找到迷宫中的路径。

4) 使用递归算法找到迷宫中的路径。

5) 比较不同算法的性能和效率。

6) 记录实验结果并进行分析。

3.结果与分析3.1 实验结果在我们的实验中，我们使用了一个10x10的迷宫进行测试。

我们比较了深度优先搜索、广度优先搜索和递归算法的性能。

深度优先搜索算法找到的最短路径长度为14步，搜索时间为0.15秒。

广度优先搜索算法找到的最短路径长度为14步，搜索时间为0.18秒。

递归算法找到的最短路径长度为14步，搜索时间为0.12秒。

3.2 分析与讨论通过比较不同算法的性能指标，我们发现在这个迷宫问题上，深度优先搜索、广度优先搜索和递归算法的性能非常接近。

它们在找到最短路径的长度和搜索时间上都没有明显差异。

4.结论与建议根据本次实验的结果，我们可以得出以下结论：●深度优先搜索、广度优先搜索和递归算法都可以成功解决迷宫问题。

●在这个具体的迷宫问题上，这些算法的性能差异不大。

在进一步研究和实验中，我们建议考虑更复杂的迷宫结构和更多的搜索算法，以探索它们在不同情况下的性能差异。

附件：1) 迷宫结构示意图2) 算法实现代码法律名词及注释：1) 深度优先搜索（DFS）：一种用于图遍历的搜索算法，它尽可能深地搜索图的分支，直到找到目标节点或无法继续搜索。

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

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

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

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

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