搜索
罗密欧与朱丽叶的迷宫问题河南科技大学课程设计报告课程名称：软件专题训练设计题目：罗密欧与朱丽叶的迷宫问题院系：专业：班级：学生姓名:学号:起止日期:2012年5月21日~2012年5月27日指导教师:罗密欧与朱丽叶的迷宫问题I课程设计题目罗密欧与朱丽叶的迷宫问题姓名学号班级系别专业组别组长组员指导教师姓名课程设计目的进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。设计环境1.PC兼容机2．Windows2000/XP操作系统3．TC集成开发环境或其他C语言开发环境课程设计要求和任务要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题；2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存到文件中；3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。4．对系统进行功能模块分析、画出总流程图和各模块流程图；5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单；6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块；7．所有程序需调试通过。任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括：1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线；2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。课程设计工作进度计划序号起止日期工作内容12012.5.21下发任务书，分组，选定课题，查阅相关资料22012.5.22总体设计，划分模块，编制源程序32012.5.23上机调试，修改、完善系统42012.5.25程序检查，撰写说明书，上交报告罗密欧与朱丽叶的迷宫问题II第一章需求分析1.1课程设计题目对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少弯道路程序能够演示一条罗密欧找到朱丽叶的路线过程等1.2课程设计任务及要求罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的。(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。1.3软硬件运行环境及开发工具硬件：装有windows操作系统的计算机软件：VisualC++6.0罗密欧与朱丽叶的迷宫问题III第二章程序概要设计2.1系统流程图2.2函数的划分：（1）函数1：booltrackback(intx,inty)递归调用trackback函数求出最优路径。（2）函数2：voidisfull()判断房间是否全部走完（3）函数3：voidmain()主函数初始化迷宫数组，并调用trackback函数输出一条迷宫路线。输入m,n,k,p,q,r,s-1-dirscount-0dep=m*n-k&&x=r&&y=s&&dirs=best是否dep=m*n-k||x=r&&y=s||dirsbest是否dirsbest是否是否Count+1-countbest=dirs;count=1;1-.i1-jbestw[i][j]=board[i][j]+1-j直到j=ni=i-i直到i=mzzhaireturnreturn1-ip=x+dir[i][0]q=y+dir[i][1]x0&&x=m&&y0&&y=n&&board[x][y]=0是di!=i是dirs-1-dirsboard[p][q]=0;board[p][q]=dep+1di!=idirs+1-dis直到ri=8输出best,count**bestw罗密欧与朱丽叶的迷宫问题IV2.3．函数之间的关系：如下图：main函数isfull函数调用trackbask函数递归调用trackbask函数输出结果第三章编写代码及运行程序3.1源程序#includeiostreamusingnamespacestd;intdir[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};intcount;intdirs,best;intboard[20][20],bestw[20][20];intm,n,k;intsx,sy,ex,ey;boolcomp(intx,inty){if(x0&&x=n&&y0&&y=m&&board[x][y]==0)returntrue;elsereturnfalse;}//save保存找到的解voidsave(){inti,j;for(i=1;i=n;i++)罗密欧与朱丽叶的迷宫问题Vfor(j=1;j=m;j++)bestw[i][j]=board[i][j];}//在当前位置按照8个方向搜索voidsearch(intdep,intx,inty,intdi){if(dep==m*n-k&&x==ex&&y==ey&&dirs=best){if(dirsbest){best=dirs;count=1;save();}elsecount++;return;}if(dep==m*n-k||x==ex&&y==ey||dirsbest)return;else{for(inti=1;i=8;i++)if(comp(x+dir[i][0],y+dir[i][1])){board[x+dir[i][0]][y+dir[i][1]]=dep+1;if(di!=i)dirs++;search(dep+1,x+dir[i][0],y+dir[i][1],i);if(di!=i)dirs--;board[x+dir[i][0]][y+dir[i][1]]=0;}}}intmain(){cout输入迷宫的行数，列数，封锁房间数：endl;cinnmk;inti,j;intc,d;memset(board,0,sizeof(board));cout输入k个封锁房间的坐标x,y：endl;for(i=0;ik;i++){cincd;board[c][d]=-1;罗密欧与朱丽叶的迷宫问题VI}cout输入罗密欧的坐标：endl;cinsxsy;cout输入朱丽叶的坐标：endl;cinexey;board[sx][sy]=1;best=m*n;dirs=-1;search(1,sx,sy,0);cout最少转弯次数：endl;coutbestendl;cout不同的最少转弯道路数endl;coutcountendl;printf(遍历过程如下：);for(i=1;i=n;i++){for(j=1;j=m;j++)coutbestw[i][j];coutendl;}}3.2操作及运作结果输入输出并显示迷宫结果如下：罗密欧与朱丽叶的迷宫问题VII3.4设计的心得体会通过本次课程设计的训练，增加了我学习算法的兴趣，虽然还不是很明白其中的具体内容，但已发现算法分析与程序设计的乐趣。老师给了我们四个题目供选择，从选题到完成程序一步步操作实验不仅对题目有了深入的了解，还达到了熟练使用C语言编程的能力。虽然还有很多复杂的问题是我们的能力所不及的，但我相信通过一次次实际的训练操作会使我们的解决问题的能力一步步有所提高。这次程序设计是让我们学到了好多知识，但也暴露了我们在程序设计中的不足。让我们更深一步体会到了上机实训的重要性。学校给我们安排实训是为培养学生在实践中培养独立分析问题和解决问题的作风和能力，提高实际操作水。让我们了解到除了学习基础知识之外上机实验也是必不可少的，只有通过多次的操作实验才能够提高自己的解决问题能力.致谢在这篇论文即将完成之时，我要在这里特别的感谢一下在我的课程设计过程中帮助和关心过我的老师和同学。在设计的整个实验过程中，孙士保老师给了我很多的关心和帮助。孙老师态度谦逊、专业知识深厚，在技术方面有很深的造诣,对我的设计工作给予了极大的支持和最热诚的帮助。他严谨的治学态度、亲和的工作作风以及深厚的科研知识，都给我留下了深刻的印象。从孙老师身上，我学到了很多东西，不仅是学术知识，还有工作方式、治学态度等。同学们在我整个设计、安装、调试过程中，给了我很多非常好的建议和帮助，使我能顺利地完成课题的实际操作工作。还有同组的同学，都对我给予了帮助，在此一并表示感谢。最后，再一次向所有关心过我、帮助过我的老师和同学送上最深的谢意和最真挚的祝福！罗密欧与朱丽叶的迷宫问题VIII参考文献计算机算法设计与分析教材（第三版）c/c++程序设计教程（第二版）数据结构（C语言版）教材附录#includeiostreamusingnamespacestd;intdir[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};intcount;intdirs,best;intboard[20][20],bestw[20][20];intm,n,k;intsx,sy,ex,ey;boolcomp(intx,inty){if(x0&&x=n&&y0&&y=m&&board[x][y]==0)returntrue;elsereturnfalse;}//save保存找到的解voidsave(){inti,j;for(i=1;i=n;i++)for(j=1;j=m;j++)bestw[i][j]=board[i][j];}//在当前位置按照8个方向搜索voidsearch(intdep,intx,inty,intdi){if(dep==m*n-k&&x==ex&&y==ey&&dirs=best){if(dirsbest){罗密欧与朱丽叶的迷宫问题IXbest=dirs;count=1;save();}elsecount++;return;}if(dep==m*n-k||x==ex&&y==ey||dirsbest)return;else{for(inti=1;i=8;i++)if(comp(x+dir[i][0],y+dir[i][1])){board[x+dir[i][0]][y+dir[i][1]]=dep+1;if(di!=i)dirs++;search(dep+1,x+dir[i][0],y+dir[i][1],i);if(di!=i)dirs--;board[x+dir[i][0]][y+dir[i][1]]=0;}}}intmain(){cout输入迷宫的行数，列数，封锁房间数：endl;cinnmk;inti,j;intc,d;memset(board,0,sizeof(board));cout输入k个封锁房间的坐标x,y：endl;for(i=0;ik;i++){cincd;board[c][d]=-1;}cout输入罗密欧的坐标：endl;cinsxsy;cout输入朱丽叶的坐标：endl;cinexey;board[sx][sy]=1;best=m*n;dirs=-1;search(1,sx,sy,0);cout最少转弯次数：endl;罗密欧与朱丽叶的迷宫问题Xcoutbesten