罗密欧与朱丽叶迷宫课程设计报告

1、最新资料推荐课程设计报告文档题目：罗密欧与朱丽叶的迷宫问题一任务的描述1问题描述：罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m n 的迷宫中。每一个方格表示迷宫中的一个房间。这mn 个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p ，q) 方格中，他必须找出一条通向朱丽叶所在的(r ，s) 方格的路。 在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最

2、少转弯道路。输入数据：第一行有 3 个正整数 n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的 k 行中，每行 2 个正整数，表示被封闭的房间所在的行号和列号。最后的2 行，每行也有2 个正整数，分别表示罗密欧所处的方格(p ， q) 和朱丽叶所处的方格(r ， s) 。结果输出 : 将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路。文件的第一行是最少转弯次数。文件的第2 行是不同的最少转弯道路数。接下来的n 行每行 m 个数，表示迷宫的一条最少转弯道路。aij=k表示第 k 步到达方格 (i,j) ；aij=-1表示方格 (i,j) 是封闭的。如果罗密欧无法通

3、向朱丽叶则输出“nosolution!”。输入文件示例43212341 12 2输出文件示例671-19821067345-12 任务目标：（ 1）确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线；（2）程序能够演示一条罗密欧找到朱丽叶的路线过程等。3运行环境：vc+6.0二任务设计1系统流程图：程序概要的流程图如下：1最新资料推荐数据初始化得到罗密欧位置沿八个方向搜索否是否满足剪枝函数是沿该方向深度搜索否继续朝其它方是否得到一个解向搜索是与当前最优解比较，适时更新2函数的划分：（1）函数 1：void print() / 调用自动显示函数 au()和动态显示函数 dynamic(

4、)，输出一条转弯最少的路径（ 2）函数 2： void search(intdep ,int x,int y,int di); / 执行搜索，结果保存在bestb二维数组中，供输出使用（ 3）函数 3： boolconsistant(int x ,int y,int dep) /约束剪枝函数（ 4）函数 4： void save(); /save保存找到的最优路线（ 5）函数 5： int stepok(int x,int y);/ 用于判断是否越界和可通过（ 6）函数 6： void au()/ 自动显示一条路径（ 7）函数 7： void dynamic()/ 动态显示一条路径（ 8）函数

5、 8： void init()/ 完成数据输入2最新资料推荐（ 9）函数 9： int main(); / 主函数 ,调用 init() 和 search()及 print() ，实现相应的功能3函数之间的关系：从主函数开始运行，调用 init() 函数，输入迷宫行数列数封闭房间数，输入 罗 密 欧 与 朱 丽 叶 坐 标 后 输 出 迷 宫 图 ； 然 后 开 始 执 行 搜 索 函 数 search(int ,int,int,int) ，进行搜索，在搜索函数中会调用剪枝函数 consistant()和 stepok()及保存函数 save()，将路径保存在 bestb 矩阵当中；由 pri

6、nt() 函数调用 au() 和 dynamic() 函数，将找到的一条路径在屏幕上动态地输出；三分组情况本人组长负责执行搜索模块，其他两人分别实现自动显示和动态显示四编写代码1问题 1（1）问题描述：程序需要处理不同的迷宫大小（2）解决办法：可以预先分配很大的内存空间和动态地分配一个矩阵数组给予解决，这里采用动态分配方式，提高空间利用率2问题 2（1）问题描述：执行搜索时，最少转弯数运行结果不对（2）解决办法：反复检查，没能理解题意，第一步应该可以朝任何方向而都不算转弯才对，于是在判断是否转弯时，还得判断是否为第一步才行3问题 3（1）问题描述：执行效率在迷宫较大且可通过房间数很多时低的难以

7、想象（2）解决办法：通过对搜索过程仔细反复研究，进一步挖掘出限制条件，增强剪枝功能，当迷宫较大且封闭房间数较多或较密集时，明显提高了搜索效率五程序运行1自动显示功能：3最新资料推荐4最新资料推荐2动态显示功能：六、感想认识通过本次训练，让我体会到这样一个事实，对问题本身掌握的信息越多，就越有可能设计出较好的算法和实现方法，而通用方法比如 “万能的” 回溯法必须经过具体问题的改造才有可能得到满意的结果；算法设计也得 “拳不离手曲不离口”，否则也会生疏而进展缓慢。参考文献：1 王晓东 .计算机算法设计与分析第三版 . 北京 : 电子工业出版社 , 2007,52 严蔚敏，吴伟民 .数据结构 (c

8、语言版 ) 北京 : 清华大学出版社 , 20073 林华聪 . c 语言程序设计思想与实践.北京 : 冶金工业出版社,20024 (美 )nicholas a.solter , scott j.kleper 著， c+ 高级编程 .刘鑫，杨建康等译 .北京：机械工业出版社， 2006,15最新资料推荐附录：源程序#include#include #include#include using namespace std;/* 全局变量 */int *board;/ 指向访问的标志若以访问记录次序int *bestb;/ 指向一个最优值int *dtp;/ 在动态输出时的辅助数组int m,n,

9、k;/ 列，行，封闭房间的数目int x,y;/ 罗密欧的行列号int x1,y1;/ 朱丽叶的行列号int count=0;/ 最优解的个数int best=1000;/ 最优解int dirs=0;/ 当前最优解int dx8=-1,-1,-1,0,1,1, 1, 0;/ 从该节点依次从左上方开始顺时针搜索 int dy8=-1, 0, 1,1,1,0,-1,-1;bool stepok(int x,int y) / 边界函数/没加外围“墙”return(x=0 & x=0 & ym & boardxy=0);void save() / 保存函数for(int i=0;in;i+)for(

10、int j=0;jm;j+)bestbij=boardij; /连 -1一块保存bool consistant(int x,int y,intdep) /约束剪枝函数int i=0,j=0,num1=0,num2=0;if(stepok(x, y)boardxy=1;/ 假设该节点为活结点for(i=0;i8;i+) /从周围八个方向开始考察if(stepok(x+dxi,y+dyi)6最新资料推荐for(j=0;j8;j+)if(stepok(x+dxj,y+dyj) num1+; /统计可选的通道数if(num1=0&dep=2)boardxy=0;return false; /复位voi

11、d search(int dep,int x,int y,int di)int i;if(dep=(m*n-k)&(x=(x1-1)&y=(y1-1)&(dirs=best)/得到一个可选解if(dirsbest) return;/一般约束elsefor(i=0;i8;i+)if(stepok(x+dxi,y+dyi)&consistant(x+dxi,y+dyi,dep)boardx+dxiy+dyi=dep+1;if(di!=i&dep!=1)dirs+;search(dep+1,x+dxi,y+dyi,i);if(di!=i&dep!=1) dirs-; /回溯boardx+dxiy+d

12、yi=0;7最新资料推荐/cout 第 dep 层 endl;/sleep(3000);/void au()int i,j;for( i=0;in;i+)/静态显示迷宫for(j=0;jm;j+)cout.width(6);coutbestbij;coutn;cout 输出拐弯数：;coutbest;coutn;cout 输出路径数：;coutcount;coutn;cout 以下自动演示endl;for(int a=1;a=m*n-k;a+)for( i=0;in;i+)/静态显示迷宫for(j=0;jm;j+)if(bestbij=a) /打印出 1-a 的步数cout.width(6);

13、coutbestbij;elsecout.width(6);coutboardij;coutn;8最新资料推荐cout 下一步 :n;sleep(1800);void dynamic()int i,j;for(int a=1;a=m*n-k;a+)for( i=0;in;i+)for(j=0;jm;j+)if(bestbij=a) /打印出 1-a 的步数cout.width(6);coutbestbij;elsecout.width(6);coutboardij;coutn;cout 请按任意键继续:n;getchar();void print()/ 显示迷宫路径while(1) coute

14、ndl 选择 操作 endl;cout0退出 endl;cout1单步 endl;cout2自动 choose;switch(choose)case 0: return;case 1: dynamic();break;case 2 : au();break;void init()9最新资料推荐/ifstream in(data.txt);/测试时间数据/ ofstream out(result.txt); int i,j;int p,q;coutnmk;board=new int*n;bestb=new int*n;dtp=new int*n;for(i=0;in;i+)boardi=new intm;bestbi=new intm;dtpi=new intm;for( i=0;in;i+)for(j=0;jm;j+)boardij=0;bestbij=0;cout 输入封闭空间的行列号n;for(i=0;ipq;boardp-1q-1=-1;dtpp-1q-1=-1;for