迷宫课程设计

PAGEPAGE20暑期课程设计题目：多功能迷宫游戏学院：计算机与信息学院班级：信息112姓名：郑少飞学号：3110702228目录一、前言………2二、问题背景…………………2三、问题分析…………………2四、试探方向…………………2五、求解算法…………………3六、程序代码…………………4七、运行结果…………………18一．前言：学院安排的暑期课程设计是对我们学生的专业知识和动手实践能力的一次颇有益处的检验。院老师为我们制定了众多的课题，由我们自己根据自身能力与专长进行选择，培养分析问题、解决问题能力。即使是一个简单的程序，依然需要学生有条不理的构思。有利于培养严谨认真的学习态度，在程序设计过程里，当我们输入程序代码的时候，如果不够认真或细心，那么可能就导致语法错误，从而无法得出运行结果。那么，这个我们反复调试，反复修改的过程，其实也是对我们认真严谨治学的一个锻炼。在设计的过程中，会碰到某些必须加以克服的困难和障碍，这些困难构成真正的、我们渴望以挑战而接受的问题。在攻克这些难题，寻找解决它们的办法时，我们自身的能力得到很大程度的提高，让我们体会到治学态度端正的重要性。二：问题背景：迷宫求解是实验心理学中的一个经典问题，心理学家把一只小老鼠从一个无顶盖的盒子的入口赶进迷宫，迷宫中设置很多墙壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，便由此衍生出了迷宫求解问题！三：问题分析迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。回溯法是一种不断试探与及时纠错的探索方法，

为便于回溯，对于可走的方块都要进栈，并试探它的下一个可走方位，将这个可走的方位保存到栈中求解路径过程为：先将入口进栈（初始方位设置为-1），在栈不为空时循环：取栈顶方块（不退栈），若是出口，则输出栈中方块即为路径。否则，找下一个可走的相邻方块，若不存在这样的方块，则退栈。若存在，即将其方位保存到栈顶元素中，并将这个可走相邻方块进栈（初始方位设置为-1）。四：试探方向在迷宫中，每个点有四个方向可以去试探，如果当前点的坐标（x，y），与其相邻的四个点的坐标都可以根据与该点的相邻方位而得到，如下图：（x，y）（x，y）（x-1，y）（x，y-1）（x+1，y）（x，y+1）因为出口在（m，n），因此试探规则为：从当前的位置向前试探的方向从正东为从正东顺时针方向进行。为了简化问题，方便求出新点的坐标，将从正东开始顺时针进行的这四个方向的坐标增量放在一个结构数组move【4】中，在move数组中，每个元素有两个域组成，x为横坐标增量，y为纵坐标增增量，move数组如图：XY数组下标0101010-12-103Move数组定义如下：Typedefstruct{intx，y；}item；Itemmove[4]；五：求解算法：（1）栈初始化；（2）将入口点坐标及到达该点的方向（设为-1）入栈；（3）while（栈不空）{栈顶元素>=（x,y,d）出栈；求出下一个要试探的方向d++；While（还有剩余的试探方向时）{If（d方向可走）{（x,y,d）入栈；求新点坐标（i，j）；将新点坐标（i,j）切换为当前点（x,y）;If（(x,y)==(m,n)）{结束；}Else{重置d=0；}}Else{D++；}}}六：程序代码：#include<iostream>#include<string.h>#include<fstream>#include<stdio.h>#include<malloc.h>usingnamespacestd;#definemaxsize100intmi_gong[maxsize][maxsize];//定义迷宫，此迷宫中0代表有路径1代表没有路径inthang_shu;//行数intlie_shu;//列数charjian_li_mi_gong_fang_shi;//建立迷宫的方式选择，1代表手动2代表自动（用了文件流）intji_cun[maxsize][maxsize];intzhao_dao=0;typedefstruct{intzong;//纵intheng;//横}cun_chu_zuo_biao;cun_chu_zuo_biaocun_chu[maxsize];/*接下来定义栈*/typedefstruct{intx;inty;intd;}datatype;typedefstruct{datatypedata[maxsize];inttop;}seqstack,*pseqstack;/*定义栈完成*//*接下来定义增量数组*/typedefstruct{intx;inty;}item;/*定义增量数组完成*//*接下来栈的初始化*/pseqstackinit_seqstack(void){pseqstacks;s=(pseqstack)malloc(sizeof(seqstack));if(s){s->top=-1;}returns;}/*栈的初始化完成*//*接下来判断栈空*/intempty_seqstack(pseqstacks){if(s->top==-1){return1;}else{return0;}}/*判断栈空完成*//*接下来入栈*/voidpush_seqstack(pseqstacks,datatypex){if(s->top==maxsize-1){cout<<"栈满！！！"<<endl;}else{s->top++;s->data[s->top]=x;}}/*入栈完成*//*接下来是出栈*/datatypepop_seqstack(pseqstacks){datatypex;if(empty_seqstack(s)){cout<<"栈空！！！！"<<endl;}else{x=s->data[s->top];s->top--;}returnx;}/*出栈完成*/voidkai_shi_jie_mian()//开始的欢迎界面{ charb=3; chara=5; cout<<"\n\n"; cout<<""; for(intbb=0;bb<60;bb++) { cout<<b; } for(bb=1;bb<=5;bb++) { cout<<"\n"; cout<<""; cout<<a; cout<<""; cout<<a; } cout<<"\n"; cout<<""; cout<<a; cout<<"迷宫演示系统欢迎您的到来"; cout<<a; for(bb=1;bb<=5;bb++) { cout<<"\n"; cout<<""; cout<<a; cout<<""; cout<<a; } cout<<"\n"; cout<<""; for(bb=0;bb<60;bb++) { cout<<b; } cout<<endl; cout<<"\n\n";}voidzeng_liang_shu_zu_chu_shi_hua(itemmove[4]){charxi_shou='0';intcount2=0;charch;//控制优先级方向charchong_xin_xuan_ze='Y';//重新选择标志cout<<"_______________________________________________________________________________"<<endl;cout<<"操作说明如下："<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正东方向请按E"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正南方向请按S"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正西方向请按W"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正北方向请按N"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cin>>ch;while(chong_xin_xuan_ze=='Y'){if(count2>=1){cout<<"_______________________________________________________________________________"<<endl;cout<<"操作说明如下："<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正东方向请按E"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正南方向请按S"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正西方向请按W"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"优先方向为正北方向请按N"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"\n\n"; cin>>ch;}switch(ch){case'E':{move[0].x=0;//增量数组初始化，代表四个方向move[0].y=1;move[1].x=1;move[1].y=0;move[2].x=0;move[2].y=-1;move[3].x=-1;move[3].y=0;//增量数组初始化结束chong_xin_xuan_ze='N';break;}case'S':{move[0].x=1;//增量数组初始化，代表四个方向move[0].y=0;move[1].x=0;move[1].y=-1;move[2].x=-1;move[2].y=0;move[3].x=0;move[3].y=1;//增量数组初始化结束chong_xin_xuan_ze='N';break;}case'W':{move[0].x=0;//增量数组初始化，代表四个方向move[0].y=-1;move[1].x=-1;move[1].y=0;move[2].x=0;move[2].y=1;move[3].x=1;move[3].y=0;//增量数组初始化结束chong_xin_xuan_ze='N';break;}case'N':{move[0].x=-1;//增量数组初始化，代表四个方向move[0].y=0;move[1].x=0;move[1].y=1;move[2].x=1;move[2].y=0;move[3].x=0;move[3].y=-1;//增量数组初始化结束chong_xin_xuan_ze='N';break;}default:{count2++;cout<<"选择方向优先级错误！请您重新选择!!\n\n\n"<<endl;chong_xin_xuan_ze='Y';}}}}voidjian_li_mi_gong_wen_jian_liu(inthang_shu,intlie_shu)//用文件流建立迷宫{intc;ifstreaminfile[99];infile[0].open("migong2-2.txt",ios::in);infile[1].open("migong2-3.txt",ios::in);infile[2].open("migong2-4.txt",ios::in);infile[3].open("migong2-5.txt",ios::in);infile[4].open("migong2-6.txt",ios::in);infile[5].open("migong2-7.txt",ios::in);infile[6].open("migong2-8.txt",ios::in);infile[7].open("migong2-9.txt",ios::in);infile[8].open("migong2-10.txt",ios::in);infile[9].open("migong3-2.txt",ios::in);infile[10].open("migong3-3.txt",ios::in);infile[11].open("migong3-4.txt",ios::in);infile[12].open("migong3-5.txt",ios::in);infile[13].open("migong3-6.txt",ios::in);infile[14].open("migong3-7.txt",ios::in);infile[15].open("migong3-8.txt",ios::in);infile[16].open("migong3-9.txt",ios::in);infile[17].open("migong3-10.txt",ios::in);infile[18].open("migong4-2.txt",ios::in);infile[19].open("migong4-3.txt",ios::in);infile[20].open("migong4-4.txt",ios::in);infile[21].open("migong4-5.txt",ios::in);infile[22].open("migong4-6.txt",ios::in);infile[23].open("migong4-7.txt",ios::in);infile[24].open("migong4-8.txt",ios::in);infile[25].open("migong4-9.txt",ios::in);infile[26].open("migong4-10.txt",ios::in);infile[27].open("migong5-2.txt",ios::in);infile[28].open("migong5-3.txt",ios::in);infile[29].open("migong5-4.txt",ios::in);infile[30].open("migong5-5.txt",ios::in);infile[31].open("migong5-6.txt",ios::in);infile[32].open("migong5-7.txt",ios::in);infile[33].open("migong5-8.txt",ios::in);infile[34].open("migong5-9.txt",ios::in);infile[35].open("migong5-10.txt",ios::in);infile[36].open("migong6-2.txt",ios::in);infile[37].open("migong6-3.txt",ios::in);infile[38].open("migong6-4.txt",ios::in);infile[39].open("migong6-5.txt",ios::in);infile[40].open("migong6-6.txt",ios::in);infile[41].open("migong6-7.txt",ios::in);infile[42].open("migong6-8.txt",ios::in);infile[43].open("migong6-9.txt",ios::in);infile[44].open("migong6-10.txt",ios::in);infile[45].open("migong7-2.txt",ios::in);infile[46].open("migong7-3.txt",ios::in);infile[47].open("migong7-4.txt",ios::in);infile[48].open("migong7-5.txt",ios::in);infile[49].open("migong7-6.txt",ios::in);infile[50].open("migong7-7.txt",ios::in);infile[51].open("migong7-8.txt",ios::in);infile[52].open("migong7-9.txt",ios::in);infile[53].open("migong7-10.txt",ios::in);infile[54].open("migong8-2.txt",ios::in);infile[55].open("migong8-3.txt",ios::in);infile[56].open("migong8-4.txt",ios::in);infile[57].open("migong8-5.txt",ios::in);infile[58].open("migong8-6.txt",ios::in);infile[59].open("migong8-7.txt",ios::in);infile[60].open("migong8-8.txt",ios::in);infile[61].open("migong8-9.txt",ios::in);infile[62].open("migong8-10.txt",ios::in);infile[63].open("migong9-2.txt",ios::in);infile[64].open("migong9-3.txt",ios::in);infile[65].open("migong9-4.txt",ios::in);infile[66].open("migong9-5.txt",ios::in);infile[67].open("migong9-6.txt",ios::in);infile[68].open("migong9-7.txt",ios::in);infile[69].open("migong9-8.txt",ios::in);infile[70].open("migong9-9.txt",ios::in);infile[71].open("migong9-10.txt",ios::in);infile[72].open("migong10-2.txt",ios::in);infile[73].open("migong10-3.txt",ios::in);infile[74].open("migong10-4.txt",ios::in);infile[75].open("migong10-5.txt",ios::in);infile[76].open("migong10-6.txt",ios::in);infile[77].open("migong10-7.txt",ios::in);infile[78].open("migong10-8.txt",ios::in);infile[79].open("migong10-9.txt",ios::in);infile[80].open("migong10-10.txt",ios::in);for(c=0;c<99;c++){if(!infile[c]){cerr<<"openerror!"<<endl;exit(1);}}c=hang_shu*9+lie_shu-20;for(inti=1;i<=hang_shu;i++)for(inty=1;y<=lie_shu;y++){infile[c]>>mi_gong[i][y];}for(intguan=0;guan<81;guan++){infile[c].close();}}voidjian_li_mi_gong()//建立迷宫函数{memset(mi_gong,1,sizeof(mi_gong));//迷宫初始化1/*从这里开始建立迷宫*/inti=0;inty=0;intcount;//作为计数器charpan_duan_shi_fou_ji_xu='Y';//菜单选择错误的话，判断是否继续while(pan_duan_shi_fou_ji_xu=='Y'){cout<<"************************************************************"<<"\n";cout<<"******请选择建立迷宫的方式:1.手动建立2.自动建立******\n";cout<<"************************************************************"<<"\n";cin>>jian_li_mi_gong_fang_shi; switch(jian_li_mi_gong_fang_shi){case'1':{cout<<"请您输入迷宫的行数还有列数："<<endl;cin>>hang_shu>>lie_shu;count=hang_shu*lie_shu;cout<<"请输入一个行数为"<<""<<hang_shu<<""<<"列数为"<<""<<lie_shu<<""<<"的数组迷宫"<<endl;for(i=1;i<=hang_shu;i++)for(y=1;y<=lie_shu;y++){cin>>mi_gong[i][y];}getchar();cout<<"系统已经确定您建立的迷宫为：\n";for(i=1;i<=hang_shu;i++){for(y=1;y<=lie_shu;y++){cout<<mi_gong[i][y]<<"";}cout<<endl;}memcpy(ji_cun,mi_gong,sizeof(mi_gong));pan_duan_shi_fou_ji_xu='N';break;}case'2':{cout<<""<<endl;cout<<"注:考虑到迷宫的一般形式，系统要求迷宫的行列数均不小于2并且不大于10"<<endl;cout<<""<<endl;cout<<"请您按照要求输入迷宫的行数还有列数：\n";cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cin>>hang_shu>>lie_shu;getchar();//吸收掉回车键count=hang_shu*lie_shu;jian_li_mi_gong_wen_jian_liu(hang_shu,lie_shu);//用文件流建立迷宫cout<<"\n";cout<<"________________________________________________________________________________"<<endl;cout<<"********************************************************************************";cout<<"系统已经确定您建立的迷宫为：\n";for(i=1;i<=hang_shu;i++){for(y=1;y<=lie_shu;y++){cout<<mi_gong[i][y]<<"";}cout<<endl;}cout<<"********************************************************************************";pan_duan_shi_fou_ji_xu='N';break;}default:{cout<<"选择菜单错误！"<<endl;cout<<"^^^^^^^^^^^^^"<<endl;cout<<"是否重新选择？（是/Y,否/除Y以外字符表示直接退出）"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cin>>pan_duan_shi_fou_ji_xu; if(pan_duan_shi_fou_ji_xu!='Y') { exit(1); }}}}/*建立迷宫完成*/}/*找入口的函数*/intzhao_ru_kou(intcount1,intcount,inth){intb[2];for(inti=1;i<=1;i++)//为了找到迷宫入口先找第一行的所有{for(inta=1;a<=lie_shu;a++){if(mi_gong[i][a]==0&&count<=count1){zhao_dao=1;b[0]=1;b[1]=a;count++;}}}if(count<=count1){for(inti=1;i<=1;i++)//第一行没有的话找第一列{for(inta=1;a<=hang_shu;a++){if(mi_gong[a][i]==0&&count<=count1){zhao_dao=1;b[0]=a;b[1]=1;count++;}}}}if(zhao_dao==0)//行列都没有入口的话迷宫错误{cout<<"没有入口!迷宫错误!!!!"<<endl<<endl;}return*(b+h);}/*迷宫求解算法如下：*/voidmazepath(){charmei_you_ru_kou_fan_hui;intcun=0;intpan_duan_zai=0;charpan_duan_mi_gong_suan_fa_ji_xu='Y';charpan_duan_mi_gong_suan_fa_ji_xu1;intjian_tou_biao_zhi=0;intd1;inti1;intj1;intx1=0;inty1=0;intd;intcount1=1;intcount=1;intcount3=0;datatypetemp;datatypejie_shou_chu_zhan;//接收出栈的信息itemmove[4];pseqstacks;s=init_seqstack();if(!s){cout<<"初始化失败！"<<endl;}while(pan_duan_mi_gong_suan_fa_ji_xu=='Y'){next:jian_li_mi_gong();//建立迷宫YOU_XIAN_JI:zeng_liang_shu_zu_chu_shi_hua(move);//确定方向LOOP:temp.x=zhao_ru_kou(count1,count,0);//找入口if(!zhao_dao){cout<<"没有找到入口，是否返回首页继续操作？(是/Y否/N)"<<endl;cin>>mei_you_ru_kou_fan_hui;if(mei_you_ru_kou_fan_hui=='Y'){system("cls");memset(mi_gong,1,sizeof(mi_gong));gotonext;}else{gotoend;}}zhao_dao=0;//在第一次找到横坐标的时候已经被赋值为1了这里要清零temp.y=zhao_ru_kou(count1,count,1);temp.d=-1;zhao_dao=0;cout<<"***********************"<<endl;cout<<"出发点为："<<"("<<temp.x<<","<<temp.y<<")"<<endl;cout<<"***********************"<<endl;cout<<"走出迷宫的的路径为："<<endl;cout<<"^^^^^^^^^^^^^^^^^^^"<<endl;push_seqstack(s,temp);while(!empty_seqstack(s)){jie_shou_chu_zhan=pop_seqstack(s);x1=jie_shou_chu_zhan.x;y1=jie_shou_chu_zhan.y;d=jie_shou_chu_zhan.d+1;while(d<4){i1=x1+move[d].x;j1=y1+move[d].y;if(mi_gong[i1][j1]==0){temp.x=x1;temp.y=y1;temp.d=d;push_seqstack(s,temp);x1=i1;y1=j1;mi_gong[x1][y1]=-1;if(x1==hang_shu&&y1==lie_shu){count3++;temp.x=x1;temp.y=y1;temp.d=d;push_seqstack(s,temp);while(!empty_seqstack(s)){jie_shou_chu_zhan=pop_seqstack(s);cun_chu[cun].heng=jie_shou_chu_zhan.x;cun_chu[cun].zong=jie_shou_chu_zhan.y;cun++;}for(d1=cun-1;d1>=0;d1--){if(jian_tou_biao_zhi){cout<<"-->";}else{jian_tou_biao_zhi=1;}cout<<"("<<cun_chu[d1].heng<<","<<cun_chu[d1].zong<<")";}cout<<endl;}else{d=0;}jian_tou_biao_zhi=0;}else{d++;}}}cout<<"\n";if(count3==0){if(jian_li_mi_gong_fang_shi==2){jian_li_mi_gong_wen_jian_liu(hang_shu,lie_shu);//用文件流建立迷宫，迷宫被改动这里必须重建迷宫}else{memcpy(mi_gong,ji_cun,sizeof(ji_cun));}count1++;cout<<"SORRY!计算机已经确定从该点开始无法走出迷宫"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;cout<<"_________________________________________________________________________"<<endl;cout<<"是否返回并且继续从另外的一个可能的地点开始操作？(是/Y,否/除了Y以外的字符)"<<endl;cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;count=1;//找到第一个入口之后清零countcount1++;//第一个入口没有路径的话从另外一个入口开始cin>>pan_duan_mi_gong_suan_fa_ji_xu1;if(pan_duan_mi_gong_s