《武汉理工大学基础强化报告ACM迷宫问题》由会员分享，可在线阅读，更多相关《武汉理工大学基础强化报告ACM迷宫问题（11页珍藏版）》请在金锄头文库上搜索。
1、学号：课程设计（基础强化训练）题学专 班 姓目 院 业 级 名迷宫问题计算机科学与技术学院软件工程指导教师鄢红国2014年 7月12日课程设计任务书学生姓名： 专业班级：指导教师：鄢红国 工作单位：计算机科学与技术学院题目：迷宫问题初始条件：输入：一个5 X 5的二维数组，表示一个迷宫。数据保证有唯一解。输出:左上角到右下角的最短路径。要求完成的主要任务：（包括课程设计工作蜃及其技术要求，以及说明书撰写等具体要求）1、完成算法分析；2、给出对应的程序流程图；3、给出能正确实现的程序源码；5、给出试算截屏图；6、课程设计工作的分析与总结；7、给出不少于5篇参考文献。时间安排：2014-7-6 到
2、 2014-7-12消化资料、系统调査、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1犬指导教师签名:2014年7月 日系主任（或责任教师）签名:2013年7月 日目录45678注册资料选题描述算法分析3主函数调用各个模块3.2递归探索和最短路径的保存程序流程图程序源码试算截屏图及代码通过图分析与总结参考文献b付 * PI*丿3344567899 10迷宫问题1注册资料用户名:214165密码：guanqingl2选题题号：39842选题描述定义一个二维数组:int maze55 = 0, 1,0, 1,0, 0,o, 1,0, 0,0, 0, 0,o, 1, o,0, 0,
3、 0,I, I, 0,0, 1, 0,；它表示一个迷宫，其中的I表示墙壁，0表示可以走的路，只能横着走或竖 着走，不能斜着走，要求编程序找出从左上角到右卜角的最短路线。输入：一个5 X 5的二维数组，表示一个迷宫。数据保证有唯一解。输出：左上角到右下角的最短路径，格式如样例所示。样例输入：0 10 0 00 10 100 11100 0 0 1 0样例输出:(0, 0)(1, 0)(2, 0)1)(2, 2)3)4)(3, 4)(4, 4)3算法分析3.1主函数调用各个模块迷宫问题分为创建迷宫，探索最短路径，最后输出最短路径三个主要模块， 为了便于模块化管理，将这三部分分别编写代码，最后通过主
4、函数调用。主函数 代码如下：int main()int i,j；minn=25; memset(b,0,sizeof(b); /初始化数组置为 0 memset(c,0,sizeof(c);for(i=0;i5;i+)for(j=0;j5;j+)scanf(n%dH,&aij);b|4|4=l;tyr(O,O,l)； displayO; return 0;3.2递归探索和最短路径的保存解决迷宫问题的重点是探索最短路径，算法有很多种，我选择的是递归算法, 定义了一个moves二维数组和变量i, j相加，这样可以保证探索路径的吋候是 往四个方向探索。每次递归都利用change函数，将最短路径记录，
5、递归结束后 将最短路径保存在数组c中，最后调用display函数输出数组c,即结果。void tyr(int i,int j,int count) /count用来记录递归的次数,并与最小值比较i,j为坐标数int k;if(i=4 & j=4)if(countminn)minn=count; change();return;一次递归完成 for(k=0;k=0 & x=0 & y5 & afxlfy=O) /x, y坐标不越界biUJ=l；aij=l；COUIH+；tyr(x,y,count+1); 又走 了 一步 count;biUJ=O；aij=O;void change()int i,
6、j;for(i=0;i5;i+) for(j=0;jv5;j+) cij=bij;4程序流程图主函数初始化创建迷宫递川搜索找 到最如路径输出最短路径图1:程序流程图5程序源码#inc 1 ude# include int a77,c77,minn; intb55;int moves42= 0,-1 ,-l,0),0,l, 1,0;/* 显示 */ void display()int i,j；for(i=0;i5;i+)for(j=0;jv5;j+)if(cij=l)printf(%d, %d)n”,i,j);/*用数组c保存最短路径引void change()int i,j;fbr(i=O;i
7、5;i+)for(j=0;j5;j+) cij=bi|j；/*递归搜索*/void tyr(int i,int j,int count) /count用來记录递归的次数，并与最小值比较i,j为坐标数int k;if(i=4 & j=4)if(count=0 & x=0 & y5 & axy=0) /x, y坐标不越界bij=l；aijl=l；count+;tyr(x,y,count+1);又走了 一步count;bij=O；aiUJ=O;int main()int i,j；minn=25;memset(b,0,sizeof(b); 初始化数组置为 0memset(c,0,sizeof(c);f
8、or(i=0;i5;i+)for(j=0;j ，4，4 4,0,1,0,0丄1丄0.1,1,0,0.0,0,1.0,0,0,0,03下：资料深桂学习C+ +佬宫1.5Debug宫l_5ex贰图2：程序VC+6.0试算运行图 2 3 4 0 1214165-gxqgxqLast Loginned Time：2014-07-02 10:12:19.0Coinpare 214165and 214165GORank:111303Solved Problems ListSolved:1Submissions：1School:WHUTEmail:1445481777qq. coin图2：北大ACM网站提交
9、程序记录图Problem Status ListProblem ID:User ID: 214165Result: AcceptedFTLanguage： All 冋GoRun IDUserProblemResultMemoryTimeLanguageCode LengthSubmit Time130177932141653984Accepted148KOMSC1828B2014-07-02 10:13:05图3：北大ACM网站程序通过截图7分析与总结对最短路径的探索，主要就是探索的方式的选择，我这次选择了代码比较简 单的递归探索方式。不同的探索方式对程序的效率有很大的影响，选择合适的算 法往
10、往比编写代码的过程更重耍。在探索完成之后对数据的保存也必须考虑。虽 然这次实验的代码不是很长，但是也要有注意模块化程序的思想，并口有必要的 注释。通过这次实验，我收获了很多，比如各种探索方式，在什么情况下效率更高, 这跟上学期学习的数据结构课程有很大的关系。当然我发现了口己很多的不足, 比如之前过于注重学习各种编程语言，忽略了算法对一个程序的重耍性。在以后 的编程学习中，我应该专注于一门编程语言，强化自己对代码效率的考虑，多多 编程，提高自己对算法的思考和运用能力。参考文献1 李文新、郭炜、余华山.程序设计导引及在线实践M.北京：清华大学出版社2 谭浩强.C程序设计M.北京：清华大学出版社，2005. 严蔚敏，吴伟民.数据结构M.北京:清华大学出版社，1996.4 钟珞.计算机科学导论M.武汉：武汉理工大学出版社.5 张蕊、吕涛.C程序设计教程.武汉：华中科技大学出版社
