(最新整理)迷宫求解

1、(完整)迷宫求解(完整)迷宫求解 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)迷宫求解）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)迷宫求解的全部内容。课程设计课题申报表 系 级学生相关课程c语言指导教师学生人数1课题名称迷宫求解设计地点课题工作内容 求迷宫从入口到出口的路径，即从迷宫的入口出发，顺某

2、一方向向前探索，若能走通，则继续往前走；否则沿原路退回,换一个方向继续探索，直到所有可能的通路都探索为止。课题来源课题性质使用计算机情况软件40小时 系负责人签字： 申报人： 课程设计任务书 系 班 学号 姓名 课题名称： 迷宫求解 课题要求：给出迷宫的入口和出口及相关的通路，求出从入口到出口的路径。要求使用c语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：可以使用一个二维数组来表示迷宫，其中分别用1、0表示通与不通；算法的基本思想是：若当前位置“可通，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置

3、”， 如此重复，到达出口；若当前位置“不可通，则应顺着“来向”退回到“前一通道块”,然后朝“来向”之外的其它方向探索。若该通道块四周4个方块均“不可通”，则应从“当前路径”中删除该通道块.使用栈结构记录当前路径,当前位置入栈表示向前行，出栈则表示从当前位置退回。摘 要 本课程设计主要解决设计一个迷宫以及在给出一组入口和出口的情况下，求出一条通路的问题。在课程设计中，系统开发平台为windows 2000,程序设计语言采用visual c+6。0，数据结构采用链式栈存储结构,程序运行平台为windows 98/2000/xp。对于迷宫设计问题，首先假设了用“0”表示此道路可通，“1”表示不可通，

4、即障碍，然后采用了简单的以时间产生随机种子（0，1变量)和人工输入0-1变量的方法产生迷宫矩阵。对求解迷宫通路问题，采用“穷举求解的方法和设计一个“先进后出”的栈来存放当前位置路径,最后得出一条动态行走迷宫的通路。在程序设计中,采用了结构化与面向对象两种解决问题的方法。程序通过调试运行，初步实现了设计目标。 关键词 :迷宫求解 程序设计;visual c+6.0；链式栈存储结构；0-1；穷举求解目录1 引 言31.1 课程设计目的31.2 课程设计内容31.3 概要设计32 程序设计说明52。1 定义抽象数据类型52。2 定义栈结构体及二维数组62。3 主程序模块63 详细实现83。1 流程图

5、83.2 算法说明103。3 主要算法设计10（1） 、结构体的定义10（2)、主要函数声明11（3）、主要变量说明124 运行环境与结果134。1 运行环境134.2 运行过程中遇到的问题与处理方法134。3 运行结果与分析145 结束语21参考文献22附录：23结构化设计源程231 引 言本课程设计主要解决设计一个迷宫以及在给出入口和出口的情况下求解一条通路的问题。利用“穷举求解”的方法来判定当前位置是否可通以及利用栈“先进后出”的特点来存放当前位置可通的信息。1.1 课程设计目的在我们对一个具体的问题进行分析时，往往要抽象出一个模型，设计一个算法来实现所需要达到的功能。在此程序中，我们主

6、要是综合运用所学过的知识，回顾vc+编程的同时，熟悉并掌握数据结构中的算法分析与设计。同时,要掌握类c语言的算法转换成c程序并上机调试的基础;通过本次课程设计，进一步巩固c语言和数据结构课程所学的知识，特别是加强数据结构的理解与运用，熟悉面向对象的程序设计方法；通过此次课程设计的实践，锻炼自身程序设计的能力以及用c语言解决实际问题的能力,为以后后续课程的学习以及走上社会打好基础。1.2 课程设计内容根据对题目的分析和设想，首先,设计一个链式栈存储结构，动态的对迷宫数据进行操作（主要为入栈和出栈）;其次,定义一个二维数组和一个备份数组，用于存放迷宫数据，并在构建迷宫中，要完成对手动建立迷宫和自动

7、建立迷宫方法的设计,并能输出原始迷宫信息和原始图形信息；再次，当程序接受外部输入一组入口、出口数据后，能完成对该迷宫矩阵计算出是否存在通路的情况，若存在通路，则分别用坐标通路和图形通路输出该通路,否则输出无通路的信息；最后，设计完成实现多次输入入口和出口数据后,计算出不同结果的情况,并能分别显示出对应信息。1.3 概要设计计算机解迷宫通常用的是“穷举求解方法，即从入口出发,顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解1。可以用二维数组存储迷宫数据，通常设定入口点

8、的下标为（1，1)，出口点的下标为（n,n）。为处理方便起见,可以迷宫的四周加一圈障碍.对于迷宫任一位置，均可约定有东、南、西、北四个方向可通.最后，以方阵、坐标和图形形式输出迷宫及其通路。 2 程序设计说明2.1 定义抽象数据类型1、设定迷宫的抽象数据类型为adt maze 数据对象：d= ai，j 、,0=i=m+1，0=j=n+1，m，n=50 数据关系：r= row，col row=ai-1， j , ai，j | ai1, j， ai，jd,i=1,m+1，j=0，n+1 col= ai，j1 , ai，j | ai，j1 ，ai，j d,i=1，m+1，j=0,n+1基本操作： c

9、reate（&mazen+2，a,b)初始条件：二维数组mazea+2b+2已存在，其中自第1行至第a+1行、每行中自第1列至第b+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构造迷宫的0-1数组，以“0”表示通路，以“1”表示障碍，并在迷宫四周加上一圈障碍。prin(&mazen+2，a,b) 初始条件：迷宫maze已被赋值。 操作结果：打印maze迷宫01矩阵以及图形矩阵,表示通路,表示障碍。 mazepath( &maze,x1,x2,y1，y2)初始条件：迷宫maze已被赋值。操作结果：从入口（x1,y1）开始，判定当前位置是否可通，可通就入栈并判断下一个方向是否可

10、通 ，按具体情况做入栈和出栈处理，直到出口（x2,y2）为止。printonglu1(） 初始条件：栈stack不空。 操作结果：出栈，得到一条从入口到出口的通路printonglu2(int a，int b)初始条件：迷宫maze已存在。操作结果：若迷宫maze中存在一条通路，则按照如下规定改变迷宫maze的状态；以字符、表示当前路径上往下一位置的方向，字符“”表示出口,打印迷宫矩阵。 adt maze2.2 定义栈结构体及二维数组1、定义堆栈结构typedef struct node /堆栈结构int row； /行int col; /列struct node *next;mlink；ml

11、ink stack;/定义一个栈 2、定义二维数组 int mazem+2n+2;int backupm+2n+2; /备份数组2。3 主程序模块 main（） 设置背景颜色; 输入矩阵的大小a，b; 建立矩阵； 备份矩阵； while（k！=0) 打印原始矩阵以及图形矩阵； 输入入口和出口位置； 判定有无通路； 输出结果； 输入k值，判定下一步的操作;3 详细实现3.1 流程图 (1）主要设计思想流程如下3.1图所示：开始设计栈结构体创建迷宫矩阵设计各种所需的函数设计main函数结束图3。1 主要设计思想流程图 （2)详细设计流程图通过对本问题的分析与概括和程序的分析，可得出如下3.2图的详

12、细设计程序流程图:开始输入数组行列值建立迷宫矩阵并备份迷宫信息n打印迷宫矩阵原始信息判断变量k是否为0输入入口和出口坐标信y判断mazepath的值是否为1ny输出无通路输出坐标通路以及图形通路 程序结束用局部备份数组信息还原迷宫矩阵和全局备份数组y 图3。2 程序流程图3。2 算法说明该程序用于解决设计一个迷宫,并在此基础上给出一组入口和出口数据后能判定从该入口位置起是否有通路达到出口位置，有通路则输出坐标通路和图形通路两种方式，否则输出无通路的信息。本程序分两大模块，迷宫模块和主程序模块,迷宫模块又包括建立迷宫矩阵函数、输出迷宫矩阵原始信息函数、判断通路函数和输出最终信息函数（包括输出坐标

13、通路函数和输出图形通路函数两种）五大函数,主程序模块主要为调用函数和while语句来判定是否重复执行操作.其中建立迷宫矩阵函数包括手动建立和自动建立两种功能，手动建立即人为的输入0-1数据，直至达到二维数组大小的要求，自动建立是利用时间来产生随机种子，从而建立满足大小的二维数组矩阵；输出迷宫矩阵原始信息函数的功能是首先输出带有行列号的01矩阵，再输出以表示通路,表示障碍的图形矩阵；判断通路函数首先判定由实参传递过来的入口坐标位置是否可通,然后再决定是否将其入栈,之后再执行后续操作,即若入口可通，则入栈,然后判定该位置的四方相邻的方向，若有一个方向的相邻位置可通，则将该相邻位置入栈，依次方法穷举

14、求解下去，若能到达出口位置,最后将出口位置入栈并返回函数值“1”,否则返回函数值“0；输出坐标通路函数的功能是若存在通路，则利用栈“先进后出”的特点输出从入口到出口的一条通路；输出图形通路函数的功能是若存在通路，利用栈中元素作比较,将栈中元素的信息和二维数组作比较,将二维数组对应位置上的图形改为、并输出。在主程序中,首先调用建立迷宫矩阵函数建立一个迷宫,然后用while语句来选择是否重复执行来求取不同通路。 3.3 主要算法设计（1）、结构体的定义 typedef struct node /堆栈结构int row; /行int col; /列struct node next;mlink；mli

15、nk *stack；/定义一个栈 （2）、主要函数声明 void create（int mazen+2,int a，int b）/建立迷宫 void prin(int mazen+2,int a,int b) /打印迷宫矩阵int mazepath(int mazen+2,int x1，int x2,int y1，int y2）/判定迷宫通路void printonglu1（) /输出坐标通路void printonglu2（int a，int b) /输出图形通路void main（) /主函数 system（”color f0”）; /背景为白色 int k=1,a，b； int maze

16、m+2n+2;/迷宫矩阵 int abcm+2n+2，p，q； /备份数组以重复使用迷宫 printf（建立迷宫！!n）； printf（输入迷宫矩阵的行列数m,n！!！n”); scanf(”d%d”,a，&b）； create（maze,a，b）; /建立迷宫 for(p=0;p=a+2;p+） for（q=0;qincludeincludeiostream#include#includestdio。hdefine m 50define n 50typedef struct node /堆栈结构int row； /行int col; /列struct node next;mlink；mli

17、nk *stack；/定义一个栈int backupm+2n+2； /备份数组/*建立迷宫矩阵*/void create(int mazen+2，int a,int b)/建立迷宫int i,j,flag；srand(unsigned）time(null）)； /以时间产生随机种子for(i=0；i=a+1；i+)for(j=0；j=b+1；j+）mazeij=1;/将四周置为for（i=1;i=a;i+）for（j=1;j=b；j+)mazeij=0;/初始化矩阵backupij=0；/初始化备份矩阵printf(建立迷宫矩阵(选择或者）：n1，手动建立n2,自动建立n请输入您的选择：n”）

18、；scanf(”d”，&flag）;if（flag=1)/手动建立迷宫printf（”手动建立迷宫矩阵（0表示可通表示障碍）:n”);for（i=1;i=a；i+）for（j=1;j=b；j+）scanf(”%d”,&mazeij）；if（flag=2） /自动建立迷宫int c,i1,j1;for（c=1；c=ab;c+) /矩阵初始为“”，随机选择位置赋予一个随机的或， i1=（int)(rand（）a）+1；j1=(int）(rand（）%b）+1；mazei1j1=（int）（rand（)2); /随机矩阵这样可以产生更多的“”即通路printf(自动生成中n）;system (”pa

19、use);for（i=1;i=a;i+)for(j=1;j=a；j+）backupij=mazeij;/备份数组矩阵/*打印迷宫矩阵*void prin（int mazen+2,int a,int b）int i，j，z；printf(迷宫矩阵如下(0可通)：n ”）；for（z=1;z=b;z+) /在矩阵上方标明列号if(z10) printf(”d ,z)； else printf(”%d ，z);for(i=1;i=a;i+)printf(n”）； if(i10） printf(d ”，i); /矩阵左方标明行号else printf（d ”,i）；for（j=1;j=b;j+）pri

20、ntf（%d ,mazeij)；printf(”n迷宫图形如下(白色可通）：n）；printf（ )；for(z=1;z=b；z+） /在图形上方标明列号if（z10) printf(%d ，z); else printf（d,z);for（i=1；i=a；i+)printf（n）;if（i10) printf(”%d ,i); /矩阵左方标明行号else printf（d,i);for（j=1;jrow=x1; pcol=y1; p-next=null； stack=p; /将入口放入堆栈 mazestack-rowstack-col=1;/标志入口已访问while(（！（stackrow=

21、null&stackcol=null）&(！(stack-row=x2&stack-col=y2)/未找到出口并且堆栈不空if（mazestackrow+1stackcol=0) /下面可通p=（mlink ）malloc（sizeof(mlink）)；prow=stackrow+1;pcol=stack-col;pnext=stack; /入栈stack=p;mazestack-rowstack-col=1； /标记已访问else if（mazestack-rowstackcol+1=0) /右面位置可通p=（mlink )malloc(sizeof（mlink）；p-row=stackro

22、w；pcol=stack-col+1;pnext=stack； /入栈stack=p;mazestack-rowstack-col=1;/标记已访问else if(mazestackrow1stackcol=0) /左面可通p=（mlink *）malloc（sizeof(mlink）；p-row=stackrow-1;p-col=stack-col;p-next=stack； /入栈stack=p;mazestack-rowstack-col=1;/标记已访问else if（mazestackrowstack-col1=0）/上面可通p=（mlink )malloc(sizeof(mlink

23、);p-row=stack-row;pcol=stack-col-1；pnext=stack; /入栈stack=p;mazestack-rowstackcol=1；/标记已访问else /不可通返回上一点if （stack-next!=null） /堆栈里布置一个顶点则出栈并返回循环 p=stack; stack=stacknext； /出栈 free(p)； /释放空间else /堆栈里只有一个顶点即入口，此时若释放空间出栈会使循环 /控制语句无法比较（因为stack-col,stackrow都已不存在，) stackrow=null; stack-col=null； stacknext=

24、null;if （stackrow=x2stack-col=y2) return （1）；else return (0);else return(0）;/*输出坐标通路*/void printonglu1(）mlink q；int i=1；printf（其中的一条通道为：n）； q=stack; printf（” 出口-”）； while (q!=null） if（i%5=0) printf（n”); printf（”%d%3drow，q-col)； q=qnext； i+； printf（入口n);/*分割线*/*输出图形通路*/2时输出，时输出，时输出,时输出void printonglu

25、2(int a，int b）printf(图形通路如下:n）；int z;printf(” );for（z=1;z=b;z+） /图形上方标明列号if(z10)printf（%d ,z); else printf(”%d”,z)；int i，j;mlink *p；p=stack；backupprowp-col=6;while (pnext!=null）if(p-next-col!=null)if( p-row pnextrow ） backupp-next-rowpnext-col=5；/下一节点在下else if(p-rowrowpnextcol=2;/下一节点在上else if(pcolp-next-col） backupp-nextrowpnextcol=4;/下一节点在右else backuppnext-rowp-nextcol=3;/下一节点在左else ；p=p-next;for（i=1;i=a；i+）p