迷宫问题的关键操作要点

姓名设计题目：迷宫问题的操作设计任务(重要技术参数):学会运用数据构造建立迷宫问题，编造出迷宫并设计出走出迷宫的措施硬件环境：处理器：英特尔第三代酷睿i3-3GHz内存：4GB(三星DDR31333MHz)主硬盘：希捷ST500LM012HN-M500MBB(500GB/5400转/分)显示屏：三星SEC3649(14英寸)软件环境：操作系统：Windows864位(DirectX11)指导教师评语：1、课程设计目的构造的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本据构造中链表的创立、合并等措施以和怎样通过转化成C语言在微机上运行实现等其他方面的能力。2.1问题描述：迷宫问题是取自心理学的一种古典试验。在该试验中，把一只老鼠从一种无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一种出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以抵达出口。对同一只老鼠反复进行上述试验，一直到老鼠从入口走到出口，而不走错一步。老鼠通过多次试验最终学会走通迷宫的路线。设计一种计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。↵↵↵↵↵↵↵↵(3)用一种标志(如数字8)在迷宫中标出该条通路；3.课程设计总体方案和分析3.迷宫途径的搜索：首先从迷宫的入口开始，假如该位置就是迷宫出口，则已经找到了一条途径，搜索工作结束。否则搜索其上、下、左、右位置与否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的途径；若是障碍就选择另一种相邻的位置，并从它开始搜索途径。为防止搜索反复出现，则将已搜索过的位置标识为2,同步保留搜索痕迹，在考虑进入下一种位置搜索之前，将目前位置保留在一种队列中，假如所有相邻的非障碍位置均被搜索过，且未找到通往出口的途径，则表明不存在从入口到出口的途径。这实现的是广度优先遍历的算法，假如找到途径，则为最短途径。以矩阵00101为例，来示范一下首先，将位置(0,0)(序号0)放入队列中，其前节点为空，从它开始搜索，其标识变为2,由于其只有一种非障碍位置，因此接下来移动到(0,1)(序号1),其前节点序号为0,标识变为2,然后从(0,1)移动到(1,1)(序号2),放入队列中，其前节点序号为1,(1,1)存在(1,2)(序号3)、(2,1)(序号4)两个可移动位置，其前节点序号均为2.对于每一种非障碍位置，它的相邻非障碍节点均入队列，且它们的前节点序号均为该位置的序号，因此假如存在途径，则从出口处节点的位置，逆序就可以找到其从出口到入口的通路。如下表所示：由此可以看出，得到最短途径：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)搜索算法流程图如下所示：将(0,0)入队列YNN是杏到达迷宫处Y右边是否存在下边是否存在是否存在是否存在N1.①构建一种二维数组maze[M+2][N+2]用于存储迷宫矩阵②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值③构建一种队列用于存储迷宫途径④建立迷宫节点structpoint,用于存储迷宫中每个节点的访问状况⑤实现搜索算法⑥屏幕上显示操作菜单2.迷宫的操作{定义ij为循环变量{定义ij为循环变量②迷宫中队列出队操作③判断队列与否为空{返回head==tail的值，当队列为空时，返回0}④访问迷宫矩阵中节点voidvisitintrowintcolint⑤途径求解voidmgpath(intmaze[intmintn为障碍，则此迷宫无解，返回0,程序结束。否则访问入口节点，将入口节点判断队列与否为空，当队列不为空时，则运行如下操作：{调用dequeue()函数，将队头元素返回给p,假如p.row==m-1且p.col==n-1,即抵达出口节点，即找到了途径，结束假如p.col+1<n且maze[p.row][p.col+1]==0,阐明访问到出口(找到途径)即p.row==m-1且p.col==n-1,则逆序将途径标识为3即最终将途径图形打印出来。3.菜单项选择择☆手动生成迷宫请按：1☆自动生成迷宫请按：2☆退出请按：3{case1:请输入行列数(假如超过预设范围则提醒重新输入)}在调试过程中，首先使用的是栈进行存储，不过C:\DocmentsandSettings\nev\桌面\Dcbug\Cpp1.exe'欢迎进入迷宫求解系统NNKFKNKNNSNNSNNCNNNNKNSNNCKKNNNNSSFNNSNSNNSSRNNNNNSNNN舌动生盛类宴请接：小请选择你的操作：1请输入行数：44请输入列数：4抱歉，你输入的行列数超出预设范围<8-39,8-39>,请重新输入：请输入行数：4请输入列数：4请按行输入迷宫，B表示通路，1表示障碍：迷宫生成结果如下：迷宫入口请输入行数：44迷宫生成结果如下迷喜入口…迷宫路径为：(3.3)(1.0)(0.0)迷言通路(用☆表示)如下所示：搜狗拼音输入法全：KK欢迎进入迷宫求解系统☆☆手动生成迷言请按：1☆自动生成据言请按：2☆退出请按：3xkm**xxxmkx⁰0*xxmk***mxxxmxkmb⁰xxmm**m**xmxxxk*2请按任意健继续...北选宫无解搜物拼音输入法全：通过本次的课程设计，使我学会了怎样去组织代码量较大大程序。与此同步，也使我学会了某些对代码量较大的的程序进行编写、连接、编译运行、以和调试和修改的技巧这次的课程设计涉和到编程语言和数据构造的知识，规定和平时的实比相对较高。从本次的课程设计可以检查我们对C语言和数据构造的掌握状况，同步也检查了我们对所学习过的知识的灵活运用状况。在创新性方面，这次的课程设计虽然完毕了课程设计的任务，不过缺乏发明性的设计思想，在后来的学习过程中还得继续努力。[1].严蔚敏编著.数据构造(C语言版).清华大学出版社，2023[2].朱战立.编著.数据构造——使用C语言.西安交通大学出版社，2023[4].苏小红，孙志岗等编著.C语言大学实用教程(第2版).电子工业出版社，})if(maze[i][j]=printf}}if(maze[i][j]=printf)))}}}}}{printf('\n=====================}{printf('\n========================)print(***************************************************************rint***********************************************