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

课程设计报告文档题目：罗密欧与朱丽叶的迷宫问题一．任务的描述1．问题描述：罗密欧与朱丽叶的迷宫。

罗密欧与朱丽叶身处一个m×n的迷宫中。

每一个方格表示迷宫中的一个房间。

这m×n个房间中有一些房间是封闭的，不允许任何人进入。

在迷宫中任何位置均可沿8个方向进入未封闭的房间。

罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。

在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。

每改变一次前进方向算作转弯一次。

请设计一个算法帮助罗密欧找出这样一条道路。

对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少转弯道路。

输入数据：第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。

接下来的k行中，每行2 个正整数，表示被封闭的房间所在的行号和列号。

最后的2 行，每行也有2个正整数，分别表示罗密欧所处的方格(p，q)和朱丽叶所处的方格(r，s)。

结果输出: 将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路。

文件的第一行是最少转弯次数。

文件的第2 行是不同的最少转弯道路数。

接下来的n行每行m个数，表示迷宫的一条最少转弯道路。

A[i][j]=k表示第k步到达方格(i,j)；A[i][j]=-1 表示方格(i,j)是封闭的。

如果罗密欧无法通向朱丽叶则输出“No Solution!”。

输入文件示例4 3 21 23 41 12 2输出文件示例671 -1 9 82 10 6 73 4 5 -12任务目标：（1）确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线；（2）程序能够演示一条罗密欧找到朱丽叶的路线过程等。

3．运行环境：vc++6.0二．任务设计1．系统流程图：程序概要的流程图如下：2．函数的划分：（1）函数1：void print() //调用自动显示函数au()和动态显示函数dynamic()，输出一条转弯最少的路径（2）函数2：void search(intdep ,int x,int y,int di); //执行搜索，结果保存在bestb二维数组中，供输出使用（3）函数3：bool consistant(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）函数8：void init()//完成数据输入（9）函数9：int main(); //主函数,调用init()和search()及print()，实现相应的功能3．函数之间的关系：从主函数开始运行，调用init()函数，输入迷宫行数列数封闭房间数，输入罗密欧与朱丽叶坐标后输出迷宫图；然后开始执行搜索函数search(int ,int,int,int)，进行搜索，在搜索函数中会调用剪枝函数consistant()和StepOk()及保存函数save()，将路径保存在bestb矩阵当中；由print()函数调用au()和dynamic()函数，将找到的一条路径在屏幕上动态地输出；三．分组情况本人组长负责执行搜索模块，其他两人分别实现自动显示和动态显示四．编写代码1．问题1（1）问题描述：程序需要处理不同的迷宫大小（2）解决办法：可以预先分配很大的内存空间和动态地分配一个矩阵数组给予解决，这里采用动态分配方式，提高空间利用率2．问题2（1）问题描述：执行搜索时，最少转弯数运行结果不对（2）解决办法：反复检查，没能理解题意，第一步应该可以朝任何方向而都不算转弯才对，于是在判断是否转弯时，还得判断是否为第一步才行3．问题3（1）问题描述：执行效率在迷宫较大且可通过房间数很多时低的难以想象（2）解决办法：通过对搜索过程仔细反复研究，进一步挖掘出限制条件，增强剪枝功能，当迷宫较大且封闭房间数较多或较密集时，明显提高了搜索效率五．程序运行1．自动显示功能：2．动态显示功能：六、感想认识通过本次训练，让我体会到这样一个事实，对问题本身掌握的信息越多，就越有可能设计出较好的算法和实现方法，而通用方法比如“万能的”回溯法必须经过具体问题的改造才有可能得到满意的结果；算法设计也得“拳不离手曲不离口”，否则也会生疏而进展缓慢。

参考文献：[1]王晓东.计算机算法设计与分析—第三版. 北京: 电子工业出版社, 2007,5[2]严蔚敏，吴伟民.数据结构(c语言版) 北京: 清华大学出版社, 2007[3]林华聪. C语言程序设计思想与实践. 北京: 冶金工业出版社,2002[4](美)Nicholas A.Solter , Scott J.Kleper著，C++高级编程.刘鑫，杨建康等译.北京：机械工业出版社，2006,1附录：源程序#include<dos.h>#include <time.h>#include<windows.h>#include <iostream>using namespace std;/*全局变量*/int **board;//指向访问的标志若以访问记录次序int **bestb;//指向一个最优值int **dtp;//在动态输出时的辅助数组int m,n,k;//列，行，封闭房间的数目int x,y;//罗密欧的行列号int x1,y1;//朱丽叶的行列号int count=0;//最优解的个数int best=1000;//最优解int dirs=0;//当前最优解int dx[8]={-1,-1,-1,0,1,1, 1, 0};//从该节点依次从左上方开始顺时针搜索int dy[8]={-1, 0, 1,1,1,0,-1,-1};bool StepOk(int x,int y) //边界函数{//没加外围“墙”return(x>=0 && x<n && y>=0 && y<m && board[x][y]==0);}void save() //保存函数{for(int i=0;i<n;i++)for(int j=0;j<m;j++)bestb[i][j]=board[i][j]; //连‘-1’一块保存}bool consistant(int x,int y,int dep) //约束剪枝函数{int i=0,j=0,num1=0,num2=0;if(StepOk(x, y)){board[x][y]=1;//假设该节点为活结点for(i=0;i<8;i++) //从周围八个方向开始考察{if(StepOk(x+dx[i],y+dy[i]))for(j=0;j<8;j++){if(StepOk(x+dx[j],y+dy[j])) num1++; //统计可选的通道数}if(num1==0&&dep<=(m*n-k-2) )//当前节点不能作为活结点{board[x][y]=0;return false; //复位}if(num1==1) num2++; //统计当前节点设为活结点后，周围节点中只有一个通道的节点总数，若大于2，则当前节点显然不能作为活结点}}if(num2>=2){board[x][y]=0;return false; //复位}}}void 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(dirs<best){best=dirs;count=1;save();}else count++;return;}if(dep==(m*n-k)||x==(x1-1)&&y==(y1-1)||dirs>best) return;//一般约束else{for(i=0;i<8;i++){if(StepOk(x+dx[i],y+dy[i])&&consistant(x+dx[i],y+dy[i],dep)){board[x+dx[i]][y+dy[i]]=dep+1;if(di!=i&&dep!=1) dirs++;search(dep+1,x+dx[i],y+dy[i],i);if(di!=i&&dep!=1) dirs--; //回溯board[x+dx[i]][y+dy[i]]=0;}}//cout<<"第"<<dep<<"层"<<endl;//Sleep(3000);}////////////////////////////////////void au(){int i,j;for( i=0;i<n;i++)//静态显示迷宫{for(j=0;j<m;j++){cout.width(6);cout<<bestb[i][j];}cout<<"\n";}cout<<"输出拐弯数：";cout<<best;cout<<"\n";cout<<"输出路径数：";cout<<count;cout<<"\n";cout<<"以下自动演示"<<endl;for(int a=1;a<=m*n-k;a++){for( i=0;i<n;i++)//静态显示迷宫{for(j=0;j<m;j++){if(bestb[i][j]<=a) //打印出1-a的步数{cout.width(6);cout<<bestb[i][j];}else{cout.width(6);cout<<board[i][j];}}cout<<"\n";}cout<<"下一步:\n";Sleep(1800);}}void dynamic(){int i,j;for(int a=1;a<=m*n-k;a++){for( i=0;i<n;i++){for(j=0;j<m;j++){if(bestb[i][j]<=a) //打印出1-a的步数{cout.width(6);cout<<bestb[i][j];}else{cout.width(6);cout<<board[i][j];}}cout<<"\n";}cout<<"请按任意键继续:\n";getchar();}}void print()//显示迷宫路径{while(1){ cout<<endl<<"选择"<<"操作"<<endl;cout<<" "<<0<<" 退出"<<endl;cout<<" "<<1<<" 单步"<<endl;cout<<" "<<2<<" 自动"<<endl;int choose ;cin>>choose;switch(choose){case 0: return;case 1: {dynamic();break;}case 2 : {au();break;}}}}void init(){//ifstream in("data.txt");//测试时间数据// ofstream out("result.txt");int i,j;int p,q;cout<<"输入行数，列数，封闭房间数\n"; cin>>n>>m>>k;board=new int*[n];bestb=new int*[n];dtp=new int*[n];for(i=0;i<n;i++){board[i]=new int[m];bestb[i]=new int[m];dtp[i]=new int[m];}for( i=0;i<n;i++)for(j=0;j<m;j++){board[i][j]=0;bestb[i][j]=0;}cout<<"输入封闭空间的行列号\n";for(i=0;i<k;i++){cin>>p>>q;board[p-1][q-1]=-1;dtp[p-1][q-1]=-1;}for( i=0;i<n;i++){for(j=0;j<m;j++){cout.width(6);cout<<board[i][j];}cout<<"\n";}cout<<"输入罗密欧的行列号\n";cin>>x>>y;board[x-1][y-1]=1;cout<<"输入朱丽叶的行列号\n";cin>>x1>>y1;}void main(){init();//clock_t start,final;// start=clock();search(1,x-1,y-1,0);//final=clock();print();//cout<<"time:"<<(final-start)<<endl;}11。