罗密欧与朱丽叶迷宫求解问题

河南科技大学课程设计说明书课程名称＿＿软件专题训练＿＿＿＿题目罗密欧与朱丽叶迷宫求解问题＿院系＿电子信息工程学院计算机系＿班级＿计算机科学与技术103班＿＿学生姓名＿＿＿＿＿＿＿＿＿＿＿指导教师＿孙士保、冀治航＿＿日期＿2012.5.21—2012.5.27＿＿ 河南科技大学课程设计任务书课程名称＿＿算法设计与分析＿＿＿题目＿罗密欧与朱丽叶的迷宫问题院系＿电子信息工程学院计算机系＿班级＿＿＿计算机103班＿＿＿＿＿学生姓名＿＿＿＿魏鹏超＿＿＿＿＿＿指导教师＿孙士保、冀治航＿＿日期＿2012.5.21—2012.5.27＿＿ 罗密欧与朱丽叶的迷宫问题课程设计题目罗密欧与朱丽叶的迷宫问题姓名学号班级计算机10级系别计算机科学与技10级专业计算机科学与技术组别组长组员指导教师姓名孙士保、冀治航课程设计目的进一步巩固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程序检查，撰写说明书，上交报告4 罗密欧与朱丽叶的迷宫问题河南科技大学课程设计报告课程名称＿＿软件专题训练＿＿＿＿题目＿罗密欧与朱丽叶的迷宫问题院系：电子信息工程学院计算机系专业：计算机科学与技术班级：计算机10级学生姓名:学号:起止日期:2012年5月21日~2012年5月27日指导教师:孙士保、冀治航4 罗密欧与朱丽叶的迷宫问题目录第一章需求分析41.1课程设计题目41.2课程设计任务及要求41.3运行环境及开发工具4第二章概要设计52.1系统流程图5第三章详细设计63.1函数划分63.2函数之间的关系6第四章系统调试与操作说明74.1系统调试及操作说明7第五章课程设计总结体会85.1课程设计总结85.2致谢85.3参考文献814 罗密欧与朱丽叶的迷宫问题第一章需求分析1.1课程设计题目罗密欧与朱丽叶的迷宫问题1.2课程设计任务及要求1、对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少转弯道路2、程序能够演示一条罗密欧找到朱丽叶的路线过程等罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。1.3运行环境及开发工具硬件：装有windows操作系统的计算机软件：VisualC++6.014 罗密欧与朱丽叶的迷宫问题第一章概要设计2.1系统流程图输入m,n,k,x,y,x1,y1-1->dirsbest->1000count->0dep==m*n-k&&x==x1&&y==y1&&dirsjbestb[i][j]=board[i][j]j+1->j直到ji直到icountreturndep==m*n-k||x==x1&&y==y1||dirs>best是否1->ip=x+dx[i]q=y+dy[i]x>0&&x0&&ydirs直到idirsboard[p][q]=0;board[p][q]=dep+1di!=idirs+1->dirs直到i0&&x0&&y