迷宫问题课程设计报告

1、目第一章:设计问题描述与分析1.1.问题分析123第二章:算法设计与流程图4.456节点类型和指针类型6迷宫的操作6（1）生成迷宫6.（2）打印迷宫矩阵与字符图形7（3）迷宫求解路由求解操作7（4）打印迷宫通路坐标8（5）输出迷宫通路的字符图形8主函数91.0.第四章：使用说明1.1.第五章：测试结果1.2.19附21.9第一章：设计问题描述与分析.课程设计内容：该系统是由C语言编写的生成一个NXM（N行M列）的迷宫，完成迷宫的组织和存储，并实现迷宫路由算法。基本要求1、N和M是用户可配置的，缺省值为50和50。2、迷宫的入口和出口分别在左上角和右下角。提示：（1）可以使用二维数组mazeM+

2、2N+2表示迷宫，其中M,N为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值为1时表示该点是墙。老鼠在每一点都有4种方向可以走，可以用数组move4来表示每一个方向上的横纵坐标的偏移量，可用另一个二维数组markM+2N+2记录节点的访问情况。（2）可以选用深度优先算法或广度优先算法实行，迷宫可由自动或手动生成。测试用例应该包含有解迷宫和无解迷宫。.问题分析本程序要求实现迷宫问题的相关操作，包括迷宫的组织和存储，并实现迷宫路由算法（即查找迷宫路径）。程序所能达到的：具体包括迷宫的建立，迷宫的存储（迷宫由自动生成或手动生成），迷宫中路径的查找迷宫是一个矩形区域，迷宫存在一个入口和一个出口

3、，其内部包含了不能穿越的墙或者障碍。迷宫的建立即是建立这样一个迷宫矩阵，用于存储迷宫信息，包括可穿越的路和不可穿越的墙或者障碍，分别用0表示通路，1表示障碍。对于迷宫矩阵，用mxn的矩阵来描述，m和n分别代表迷宫的行数和列数。这样，则迷宫中的每个位置都可以用其行号和列号来指定。从入口到出口的路径是由一组位置构成的。每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的上、下、左、右的邻居。为了描述迷宫中位置（i，j）处有无障碍，规定，当位置（i，j）处有一个障碍时，其值为1，否则为0.这样迷宫就可以用0、1矩阵来描述，在构造矩阵时，为了操作方便会将矩阵四周置为1（不通）。对于查找迷宫路

4、由问题首先，考察，迷宫的入口位置，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则，考察其上、下、左、右位置上的邻居是否是障碍，若不是就移动到这个相邻位置上，然后对于这个位置开始搜索通往出口的路径。如果不成功，就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索出现重复，则将已搜索过的位置标记为1。同时为保留过搜索的痕迹，在考察相邻位置之前，将当前位置保存在一个堆栈中，如果所有相邻的非障碍位置均被搜索过，且未能找到通往出口的路径，则表明不存在从入口到出口的路径。且对于此，实现的是深度优先遍历算法，如果查找到路径，则为从入口到出口的路径。下面实现如何利用堆栈实行深度优先遍历算法

5、进行迷宫最短路径的查找。以矩阵111111110010111100101110001110010011111111首先，将位置（1，1）放入堆栈中，从它开始搜索，标记。由于其只有一个非障碍位置，所以接下来移动到（1，2），防止稍后的搜索再经过这个位置。从（1，2）移动到（2，2），放入堆栈中，（2，2）存在（2，3）、（3，2）两个可移动位置。标记已被搜索过，对于每一个非障碍位置，它的相邻非障碍节点均入队列，实现了深度优先遍历算法。所以如果存在路径，则从出口处节点的位置，逆序则可以找到其从出口到入口的通路。实现了查找路径。功能实现：1、数据输入形式和输入值的范围：生成迷宫时可选择手动或者自动生

6、成；手动输入迷宫矩阵时以0表示无障碍为通路，1表示该点有障碍为墙。所有输入中，元素的值均为整数。2、结果的输出形式：当完成迷宫生成后，会提示输入入口与出口，进入迷宫路由查找算法，如找到出口，则打印出路径矩阵坐标，并显示显示迷宫生成图形3、测试数据：a、进入界面，选择2,自动生成b、输入入口与出口c、查看结果.运行环境：运行环境为DOS第二章：算法设计与流程图.主函数的流程图:N将该位置入栈，并标记为1为通路判断入口是否循环结束无通路N栈顶位置右面可NN栈不为空且栈顶非出口 Y栈顶位置下面可栈顶位置上面可YN栈顶位曾左面可 通？栈顶出栈N栈顶Y出 口？ Y找出通路,链栈内即为循环结束图1迷宫算法

7、流程图1、为了实现上述功能，需要：构造一个二维数组mazeM+2N+2用于存储迷宫矩阵，构造一个二维数组backupM+2N+2用于备份迷宫矩阵；自动或手动生成迷宫，即为二维数组mazeM+2N+2赋值并备份；将构造一个堆栈用于存储迷宫路由；建立迷宫节点structMlink,用于存储迷宫中每个访问过的节点。实现迷宫路由算法，用深度优先遍历实现查找迷宫路径。如找到路径则显示路径，否则提示无通路。同时显示生成迷宫。在屏幕上显示操作菜单。2、本程序包含6个函数：(1)主函数main()(2)生成迷宫函数create()(3)打印迷宫矩阵与图形函数prin()(4)寻找迷宫路由Mazepath()(

8、5)输出迷宫通路坐标printonglu1()(6)输出迷宫生成图形printonglu2()各函数之间的关系如下图(图2)所示:create()函数关系图:prin()Mazepath()printonglu1(printonglu2(2各函数间关系图实现概要设计中定义的所有数据类型，对各个操作给出伪代码算法对于主程序和各个模块也给出相应的伪代码算法1 .节点类型和指针类型迷宫矩阵类型：Mlink*stack;intabcM+2N+2intmazeM+2N+2;intbackupM+2N+2;迷宫中节点类型及队列类型：structMlinkintrow,col;2 .迷宫的操作(1)生成迷宫

9、voidcreate(intmazeN+2)定义变量i,j,flag;srand(unsigned)time(NULL)全局变量堆栈，存储迷宫通路辅助数组迷宫矩阵备份矩阵，便于操作，定义为全局变量structnode*next;Mlink;以时间产生随机种子利用for初始化迷宫矩阵与备份矩阵，包括边界全置为1利用for将迷宫置为0选择迷宫生成方式1为手动生成，2为自动生成，输入值并赋给flagflag=1以i,j控制迷宫中行列数的循环输入以0表示通路，以1表示障碍,给mazeij赋值，不包括边界。循环结束，完成迷宫生成flag=2定义变量i1，j1用以接收随机值以i,j控制迷宫中行列数的循环赋

10、值操作以0表示通路，以1表示障碍用for(c=1;c<=M*N;c+)i1=(int)(rand()%M)+1;j1=(int)(rand()%N)+1;mazei1j1=int(rand()%2);随机定位矩阵一点，给mazei1j1赋一个随机值，这样可以增加迷宫通路的概率，循环结束，完成迷宫生成以i,j控制迷宫中行列数的循环赋值操作，将maze备份到backup;(2)打印迷宫矩阵与字符图形voidprin(intmazeN+2)此函数主要用于将迷宫矩阵显示出来定义变量i，j，z；for(z=1;z<=N;z+)if(z<10)printf("%d",

11、z);elseprintf("%d",z);此语句用来标明列号用for控制循环在第一重循环里，使用语句printf("n");if(i<10)printf("%d",i);elseprintf("%d",i);以此用来标明行号以i,j控制迷宫中行列数的循环操作，将mazeij显示出来并用字符口，分别代表可通与不可通（3）迷宫求解路由求解操作Mlink*p;用以操作堆栈入口若不通，return（0）否则下一步将其入栈未找到出口并且堆栈不空1）栈顶位置以下是否可通，可通则返回，否则2）,2）栈顶位置以上是否可通，

12、可通则返回，否则3）,3）栈顶位置以右是否可通，可通则返回，否则4）,4）栈顶位置以左是否可通，可通则返回，否则出栈并返回，如果栈顶为出口，return（1）；否则return（0）；（4）打印迷宫通路坐标voidprintonglu1（）Mlink*q;用以操作堆栈q=stackq不空输出q指向的坐标q=q->next（5）输出迷宫通路的字符图形voidprintonglu2（）此函数根据堆栈内栈顶与“次栈顶”的位置关系决定输出字符T,一，f或其中2=T,3=,4=f,5=J所有的操作都是在备份矩阵backup口上。出口位置输出inti，z，j；Mlink*p=stack；p不空if（

13、p->row>p->next->row）backupp->next->rowp->next->col=5;下一位置在下elseif(p->row<p->next->row)backupp->next->rowp->next->col=2;位置在上elseif(p->col>p->next->col)backupp->next->rowp->next->col=4;下一位置在右else;下一位置在左利用for循环，i，j为循环控制变量输出备份矩阵back

14、up为0是输出“口”为1是输出为2是输出“T”为3是输出“一”为4是输出«一为5是输出“为6是输出“”另外在输出语句上，与矩阵输出相同，标明了行号与列号(该功能为王教授所要求而后加的)3.主函数voidmenu()定义迷宫数组矩阵mazeM+2N+2定义辅助数组abcM+2N+2以用来在可以在第一次产生迷宫中重复选择入口与出口定义变量k以用来控制循环定义整型变量x1，y1，用于存储入口。定义整型变量x2，y2，用于存储出口。定义整型变量x用于接收mazepash的返回值。输入入口与出口。如果x=1则条用函数printonglu1();printonglu2();否则提示无通路。界面开

15、始会显示：1,手动建立2,自动建立按提示操作，输入入口与出口，回车即会看到结果第三章：调试分析在调试过程中，开始用堆栈实现了路径的查找并调试成功，但输出的结果仅仅只是路径坐标，看起来不形象，于是想到了用字符来表示图形并标出通路，虽然不是太完美，但比之之前好好多了在实现这一算法过程，注意将访问过的节点进行标记，并且在遍历过程中对矩阵数组是“破坏性”遍历，在算法完成后，矩阵已被破坏，堆栈中会存用路径，为了再原矩阵中用字符图形表示出通路，在建立矩阵后会迷宫矩阵备份一下，当然或许会有更好的处理方法。第四章：使用说明程序名为迷宫.exe,运行环境为DOS程序执行后显示：建立迷宫矩阵（选择1或者2）：1,

16、手动建立2,自动建立进请输入您的选择：在输入选择后输入数字选择执行不同的迷宫建立。按要求输入入口与出口第五章：测试结果1 .主页面图3主页面2 .选择自动建立图4迷宫自动生成中3，自动生成迷宫，上面为数组矩阵，其中0可通，1障碍。下面为字符图形，其中白色可通，黑色障碍图5打印出的迷宫矩阵与迷宫图形4，根据提示输入入口与出口6输入入口与出口5，回车后输出路径7打印出的迷宫路径6，输入一个非“0”继续图8输入非“0”继续走该迷宫7，输入入口与出口，无通路图9无通路附录1：附录2：源代码：#include<iostream>#include<>#include<>

17、#include<>#defineM20#defineN20typedefstructnode/堆栈结构introw;/行intcol;/列structnode*next;Mlink;Mlink*stack;/定义一个栈*/intbackupM+2N+2;/备份数组/*建立迷宫voidcreate(intmazeN+2)/inti,j,flag;srand(unsigned)time(NULL);/以时间产生随机种子for(i=0;i<=M+1;i+)for(j=0;j<=N+1;j+)mazeij=1;/将四周置为1for(i=1;i<=M;i+)for(j=1

18、;j<=N;j+)mazeij=0;/初始化矩阵backupij=0;/初始化备份矩阵printf("建立迷宫矩阵(选择1或者2)：n1,手动建立n2,自动建立n请输入您的选择：n");scanf("%d",&flag);if(flag=1)/手动建立迷宫printf("手动建立迷宫矩阵(0表示可通1表示障碍):n");for(i=1;i<=M;i+)for(j=1;j<=N;j+)scanf("%d",&mazeij);if(flag=2)/自动建立迷宫intc,i1,j1;fo

19、r(c=1;c<=M*N;c+)/矩阵初始为“0”，随机选择位置赋予一个随机的0或1，i1=(int)(rand()%M)+1;j1=(int)(rand()%N)+1;mazei1j1=int(rand()%2);/随机矩阵按照王教授的要求这样可以产生更多的“0”即通路printf("自动生成中n");system("pause");for(i=1;i<=M;i+)for(j=1;j<=N;j+)备份数组矩阵backupij=mazeij;/华丽的分割线 */打印迷宫矩阵*/*/*voidprin(intmazeN+2)inti,j;

20、printf("迷宫矩阵如下(0可通)：n");intz;for(z=1;z<=N;z+)/在矩阵上方标明列号if(z<10)printf("%d",z);elseprintf("%d",z);for(i=1;i<=M;i+)printf("n");if(i<10)printf("%d",i);/矩阵左方标明行号elseprintf("%d",i);for(j=1;j<=N;j+)printf("%d",mazeij);pri

21、ntf("n迷宫图形如下(白色可通)：n");printf("");for(z=1;z<=N;z+)/在图形上方标明列号if(z<10)printf("%d",z);elseprintf("%d",z);for(i=1;i<=M;i+)printf("n");if(i<10)printf("%d",i);/elseprintf("%d",i);for(j=1;j<=N;j+)if(mazeij=0)printf("i

22、f(mazeij=1)printf("矩阵左方标明行号");");/*分割线 */intMazepath(intmazeN+2,intx1,intx2,inty1,inty2)Mlink*p;if(mazex1y1=0)p=(Mlink*)malloc(sizeof(Mlink);p->row=x1;p->col=y1;p->next=NULL;stack=p;/将入口放入堆栈mazestack->rowstack->col=1;/标志入口已访问while(!(stack->row=NULL&&stack->

23、;col=NULL)&&(!(stack->row=x2&&stack->col=y2)/未找到出口并且堆栈不空if(mazestack->rowstack->col+1=0)/下面位置可通p=(Mlink*)malloc(sizeof(Mlink);p->row=stack->row;p->col=stack->col+1;p->next=stack;/入栈stack=p;mazestack->rowstack->col=1;/标记已访问elseif(mazestack->rowstack

24、->col-1=0)/上面可通p=(Mlink*)malloc(sizeof(Mlink);p->row=stack->row;p->col=stack->col-1;p->next=stack;/入栈stack=p;mazestack->rowstack->col=1;/标记已访问elseif(mazestack->row+1stack->col=0)/右面可通p=(Mlink*)malloc(sizeof(Mlink);p->row=stack->row+1;p->col=stack->col;p->

25、next=stack;/入栈stack=p;mazestack->rowstack->col=1;/标记已访问elseif(mazestack->row-1stack->col=0)/左面可通p=(Mlink*)malloc(sizeof(Mlink);p->row=stack->row-1;p->col=stack->col;p->next=stack; / 入栈stack=p;标记已访问mazestack->rowstack->col=1;/else/不可通返回上一点if(stack->next!=NULL)/堆栈里布

26、置一个顶点则出栈并返回循环p=stack;出栈堆栈里只有一个顶点即入口，此时控制语句无法比较(因为stack=stack->next;/free(p);/释放空间else/若释放空间出栈会使循环/stack->col,stack->row都已不存在，)stack->row=NULL;stack->col=NULL;stack->next=NULL;if(stack->row=x2&&stack->col=y2)return(1);elsereturn(0);elsereturn(0);/*输出坐标通路*voidprintonglu

27、1()Mlink*q;printf("其中的一条通道为：n");q=stack;printf("出口<-");while(q!=NULL)printf("(%d%3d)<-",q->row,q->col);q=q->next;printf("入口n");/*分割线*/*输出图形通路*/2时输出T,3时输出一，4时输出f,5时输出；voidprintonglu2()printf("图形通路如下：n");intz;printf("");for(z=1

28、;z<=N;z+)/图形上方标明列号if(z<10)printf("%d",z);elseprintf("%d",z);inti,j;Mlink*p;p=stack;backupp->rowp->col=6;while(p->next!=NULL)if(p->next->col!=NULL)if(p->row>p->next->row)backupp->next->rowp->next->col=5;/下一节点在下elseif(p->row<p->

29、next->row)backupp->next->rowp->next->col=2;/下一节点在上elseif(p->col>p->next->col)backupp->next->rowp->next->col=4;/下一节点在右elsebackupp->next->rowp->next->col=3;/else;p=p->next;下一节点在左for(i=1;i<=M;i+)printf("n");if(i<10)printf("%d&qu

30、ot;,i);/elseprintf("%d",i);for(j=1;j<=N;j+)if(backupij=0)printf("if(backupij=1)printf("if(backupij=2)printf("if(backupij=3)printf("if(backupij=4)printf("if(backupij=5)printf("if(backupij=6)printf("图形左方标明行号");");V)；一");T)；，");");voidmain()system("colorf0");/背景该为白色intk=1;intmazeM+2N+2