迷宫实验报告

3、迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。

（1）用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。

（2）设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。

（3）输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。

（4）要求输出模拟迷宫的二维数组；若存在最短路径，则有出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如（1,1），......，（i,j），......，（m,n）；若没有路径，则打印“No path”。

（5）迷宫的任一位置（i,j）上均有八个可移动的方向，用二维数组Direction存放八个方向的位置偏移量。

Direction[8][2]={{0,1}，{1,1}，{0，-1}，{-1，-1}，{1,-1}，{1,0}，{-1,0}，{-1,1}}； （6）为避免出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK[i][j]置为1。

（7）为了记录查找过程中到达位置（i，j）及首次到达（i,j）的前一位置（i_pre,j_pre），需要记住前一位置（i_pre,j_pre）在队列中的序号pre，即队列中数据元素应该是一个三元组（i,j,pre）。

（8）搜索过程简单下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置（i,j,pre）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，...，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。

二、实验过程及结果

一、需求分析

1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。

1

v1.0 可编辑可修改 2、以二维数组M[m+2][n+2]表示迷宫，M[i][j] 表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。

3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示： 如下所示：

4、程序完成对迷宫路径的搜索，为了更好地显示出求解结果，如果存在路径，则以长方形形式将迷宫打印出来，而不是只按步输出坐标，也便于检查路径的正确性，用特定符号标出迷宫的物理状态，其中字符“#”表示出口和入口，“<”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“No Path!”。如图所示：

2

v1.0 可编辑可修改

5、 程序执行的命令： ⑴ 创建初始化迷宫； ⑵ 搜索迷宫；

⑶ 输出搜索到的最短路径。

二、概要设计

（按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，故选择栈的操作来实现路径的存储）

1、迷宫的抽象数据类型定义： ADT Maze{

数据对象：D：={aij,Start,end|-20<=aij<20,Start,end∈{(i,j)|0≤i≤m+2,0≤j≤n+2,m,n≥0} }

数据关系：R={length，width}

length={|ai-1,aij∈D i=1,…,m+2,j=1,…,n+2} width={|aijaij-1∈D}

基本操作: SetMaze(&M)

3

初始条件：M已经定义，M的下属单元二维数组[row+2][d+2]已存在，,也已作为下属存储单元存在

操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以1表示障碍，由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完成迷宫构建

Pass(M, CurPos)

初始条件：已知目前迷宫状态及当前位置

操作结果：完成相应的搜索任务，如果可行，则返回1 NextPos(CurPos, directionr)

操作结果：返回CurPOS位置在方向direction上的下一位置 SameSeat(Path,row,col)

操作结果：若（row，col）位置是路径Path中的一个点，则返回TRUE PrintMaze(M)

初始条件：迷宫M已存在 操作结果：输出字符标示的迷宫 MazePath(M,&Path) 初始条件：迷宫M已存在

操作结果：搜索迷宫，用path返回搜索所得路径。如不存在，返回0 PrintPath(M,Path) 初始条件：迷宫M已存在

操作结果：迷宫M存在可行路径则将迷宫M及相应最短路径一起打印输出 }ADT MAZE； ⒊ 本程序模块结构 ⑴ 主函数模块 void main(){

初始化迷宫和栈； 创建迷宫；

4

输出迷宫； 搜索路径； 输出路径； ｝

⑵ 栈模块——实现栈抽象数据类型； ⑶ 迷宫模块——实现迷宫抽象数据类型； 各模块之间的调用关系如下：

迷宫模块

栈模块

三、详细设计

主程序模块

1、基本数据类型操作

⑴ 栈模块

① typedef struct{

int order; Position seat; int direction;

}SElemType;=row&&[num].==col)置为MAZE 型数据的下属单元，使得各个迷宫操作的函数参数十分散杂，调试时各参数关系不易把握。 迷宫处理 工作栈设置 2、另行设置PrintPath函数，使得终端输出更加友好，并巧妙地将迷宫以特殊、明朗的字符输出，效果更好。 3、开始出栈入栈的条件没有控制好，导致输出时不是完整路径，甚至出错。 4、选择方向时有一定策略，开始选择时按照顺时针依次读取方向，发现太耗时且效果不好，容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然5

后再东方、南方...，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会本着路径最短的原则向出口处行进，那么找到的路径自然是最短路径（之一）。 5、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比如先往东再往西南，其实是可以直接往南的，因此为了避免这种情况，在入栈时还要先进行这种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。

6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情况存在时由于不能想远离出口的方向行进而找不到路径，因此在搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时则返回SUCCESS，若未搜索到则再进行一次八个方向的搜索，即为了防止漏掉特殊情况，找到时则返回SUCCESS，由于第一搜索无结果若第二次搜索到路径也只能是特殊情况，故也应该是最短路径（之一）。

7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径，经过实验发现有很多问题难以解决，故选择了只用栈的方法来实现。 四、用户说明

⒈ 本程序的运行环境为windows 7（64位）操作系统，执行文件为数据结构迷宫.exe； ⒉ 进入演示程序后，即显示对话形式的提示操作过程， 1、提出输入迷宫的大小

2、按enter键输出随机生成的迷宫 3、按enter键开始搜索路径 搜索结果：

The Path：输出迷宫及路径或者输出No Path!

⒊ 提示输入迷宫大小后，用户输入所要处理迷宫的长row，宽col； ⒋ 提示输入迷宫后，用户将迷宫输入，0代表可行，1代表障碍； ⒌ 按任意键开始后，程序自动进行对所建迷宫的搜索，并将搜索结果； ⒍ 按任意键退出程序。

6

v1.0 可编辑可修改 五、测试结果

1、无路径：

2、找到最短路径：

7

v1.0 可编辑可修改

六、附录（源代码及注释） 8

#include \"\" #include \"\" #include \"\" #include \"\"

#define NULL 0 #define TRUE 1 #define FALSE 0 #define SUCCESS 1 #define FAIL 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define INFEASIBLE -2

#define MAXLENGTH 50 #define MAXWIDTH 50

#define STACK_INIT_SIZE 100 #define STACKINCRENT 10

=row&&[num].==col)//路径某一步所在的位置 }

}

return FALSE;

return TRUE;

num++; p++;

9

Status MazePath(MAZE M,SqStack *Path){ 10

// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 // （从栈底到栈顶），并返回SUCCESS；否则返回FAIL Position curpos; int curstep; SElemType e,te;

curpos=; // 设定\"当前位置\"为\"入口位置\" curstep=1; // 探索第一步

//第一次查找路径，设置5个方向(不远离!终点的五个方向)，若找到则返回SUCCESS do{

if(Pass(M,curpos)){ // 当前位置可通过，即是未曾走到过的通道块 }

else{ // 当前位置不能通过

if(!StackEmpty(S)){

Pop(S,&e);

while==5&&!StackEmpty(S)){ [][]=' '; // 留下足迹 =1; =curstep; =curpos;

Push(S,&e); // 加入路径 if==&&== }

curpos=NextPos(curpos,1); // 下一位置在当前位置的右下方 curstep++; // 探索下一步

// 到达终点（出口） return SUCCESS;

[][]=' '; //标记不能通过

Pop(S,&e); // 留下不能通过的标记，并退回一步

} // while if<5){

++;

GetTop(S,&te); if==5&&==2){ }

Push(S,&e); // 换下一个方向探索

curpos=NextPos,; // 当前位置设为新方向的相邻块

Pop(S,&e); ++;

} // if

} // if

} // else

}while(!StackEmpty(S));

curpos=; // 设定\"当前位置\"为\"入口位置\" curstep=1; // 探索第一步

//如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到

的特殊情况 11

do{

if(Pass(M,curpos)){ // 当前位置可通过，即是未曾走到过的通道块

[][]=' '; // 留下足迹 =1; =curstep; =curpos;

Push(S,&e); // 加入路径

12

}

if==&&== }

curpos=NextPos(curpos,1); // 下一位置是当前位置的东邻 curstep++; // 探索下一步

// 到达终点（出口）

//PrintPath(maze,S); //输出路径 return SUCCESS;

else{ // 当前位置不能通过

if(!StackEmpty(S)){

Pop(S,&e);

while==8&&!StackEmpty(S)){

[][]=' '; //标记不能通过

Pop(S,&e); // 留下不能通过的标记，并退回一步

} // while if<8){

++;

GetTop(S,&te); if==4&&==2){ }

Push(S,&e); // 换下一个方向探索

curpos=NextPos,; // 当前位置设为新方向的相邻块

Pop(S,&e); ++;

} // if

} // if

} // else

}while(!StackEmpty(S)); return FAIL;

} // MazePath

void PrintPath(MAZE M, SqStack Path){ 13

int row,col; SElemType *p=; int num=0;

if(StackEmpty(&Path)){ }

printf(\"\\nThe Path:\\n\"); for(row=0;row<+2;row++){ }

for(col=0;col<+2;col++){ }

printf(\"\\n\");

if(SameSeat(Path,row,col)){ } else

printf(\"%c \

if((row==1&&col==1)||(row==&&col==)

printf(\"# \");

printf(\"No Path!\\n\");//路径栈为空，则提示无路径 exit(OVERFLOW);

else

printf(\"> \");

num++; p++;

} //栈操作

Status InitStack(SqStack *S)//初始化栈 { }

Status StackEmpty(SqStack *S){ }

Status Push(SqStack *S,SElemType *e)//在栈顶插入新的元素，入栈 {

if(S->top-S->base>=S->stacksize) {

S->base=(SElemType if(S->top==S->base)

return TRUE;

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;

else

return FALSE;

*)realloc(S->base,(S->stacksize+STACKINCRENT)*sizeof(SElemType));//重新分配空间 14

if(!S->base)

exit(OVERFLOW);

S->top=S->base+S->stacksize;

}

}

S->stacksize+=STACKINCRENT;

*S->top++=*e; return OK;

Status GetTop(SqStack *S,SElemType *e)//从栈中取元素 { }

Status Pop(SqStack *S,SElemType *e) { }

if(S->top==S->base)

return ERROR; if(S->top==S->base)

return ERROR;

*e=*(S->top-1); return OK;

*e=*--S->top; return OK;

15