数据结构课程设计迷宫问题求解.doc

迷宫问题求解 一问题的提出： 人类建造迷宫已有5000年的历史。在世界的不同文化发展时期，这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走，寻找真相。关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是RPG玩多了）。这则神话讲的是，从前弥诺斯王统治着克里特岛。有一年，他没有给海神波塞冬送去允诺的祭物公牛，海神十分生气，决意报复。他附体在公牛身上，勾引了弥诺斯王的妻子帕西法厄王后。不久，王后生下一个牛首人身的怪物弥诺陶洛斯(Minotaur)。为了把怪物藏起来避免家丑外扬，弥诺斯王命令岛上最优秀的工匠代达罗斯造了一座迷宫：一所稀奇古怪的地下房子，走廊离亮处越来越远，根本找不到出口。发狂的弥诺陶洛斯在一堵堵墙壁之间徘徊游荡，左突右冲，以雅典王进贡的童男童女充饥。终于有一天，雅典王子忒修斯(Theseus)带着宝剑冒充进贡的童男进入迷宫。他一路退下弥诺斯王的女儿阿里阿德涅送给他的线团的线，杀死了牛头怪物弥诺陶洛斯，又沿着这根线找到出口，活着离开迷宫.一般的迷宫为二维平面图形,将迷宫的左上角作入口，右下角作出口，求出从入口点到出口点的一条通路。迷宫的大小为N×N，N预定义为常数，修改N的值可以改变迷宫的大小（只要不超过屏幕显示范围），而程序不必做修改。用白色表示可走的路，红色表示墙壁不可以通过。程序还设计了两种运行方式：一种是由系统自动运行探索，用递归方法实现；另一种是直接按结果搜索探索通路，颇有新意。 图1 迷宫的图例 图2 迷宫的求解老师指点二问题的分析： 图3 基本思想本问题的求解，关键是如何找到求解任意两个点间，按照以上基本思想而走出的路线。按照这个路线，我们可以通过图形函数来动态的显示迷宫的搜索过程。计算机解迷宫解通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路退回，换一个方向继续探索，直至出后位置，求得一条通路。假如所有可能的通路都探索到位能到达出口，则所设定的迷宫没有通路。为此，我们先要处理地图问题。将地图中有墙的地方设为1，而没墙的地方，也即可以通行的地方设为0，如：在我们的这个程序中的一个例子中，地图如下显示：图4 地图1 当然了，有了地图，下一步就是如何在地图中查询可行路线了。按照基本思想，当前已走过的可行的应设为墙，以防止在程序的搜索过程中，其又按原路返回，造成死循环。在我们的程序中，我们设走过的路的地图所在地为2，如下示：zmaprowcol=2; /* block current position */ 搜索路线，当需要一个数组来存储可行路线了，我们在程序中如下设定：struct int row; /* the row of the position */ int col; /* the col of the position */ pathmaxlength;由基本思想，搜索中按东南西北的先后顺序，我们又定义一个结构体来进行搜索中的换向，如下示：struct int row,col; offsetszdir=0,1 , /* move to east */ 1,0 , /* move to south */ 0,-1, /* move to west */ -1,0 /* move to north */ ;由于迷宫问题很悠久，解决方法也有很多，如：1、回溯回溯法使用栈的方式，这与当初忒修斯使用的方法很像，只不过这里用栈代替了英雄手中的线团。简单描述一下：每到达一个能走的新位置时都要把当前位置与来时的方向压栈，当遇到死路时就弹出栈顶位置，顺着下一方向继续走，直到到达出口（找到一条通路）或退回到入口（迷宫没有出口）时结束。若到达出口，此时从入口到出口的一条通路就保存在栈中，依次弹出并输出即可。由于刚学到栈，还不太熟悉，故我们没用这种方法。但过一段时间，我们会改成这种方法的。2、递归一般来说栈与递归是可以相互转化的，使用递归的地方都可以改成栈的方式，反过来也一样。但在求解迷宫问题时，栈与递归代表了两种不同的指导思想，如果说栈式的搜索方法象征着英雄忒修斯的话，那么使用递归法则更像一位手握大权的领导。当他站在迷宫入口处时，他才懒得亲自去走，这时这位领导会吩咐他的手下，让他们分别向着迷宫的各个方向去探索；当遇到岔路口时留一个人守在这里，再分出几股人，朝着每个方向继续探索；最后总会有一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守的人，再由这个人报告给上一个路口的人，依次层层上报，最后消息传到了领导那里，于是这位领导就顺着这条画好的通路大摇大摆地通过了迷宫。了解了这种思想后对于递归法就很好理解了。在递推的过程中实际上是系统自动地进行了压栈，而在回归时又自动地进行了弹栈，只不过这个栈位于系统的堆栈区，对普通用户来说是不可见的。a.我们用的正是这种方法，如下所示：int zfindpath(int row,int col,int erow,int ecol) int dir,row2,col2; if(row=erow)&&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; zmaprowcol=2; /* block current position */ for(dir=0;dir<=zdir;dir+) row2=row+offsetsdir.row; /* step to next space */ col2=col+offsetsdir.col; /* if want to observe the trace of the ball,you should add code after here!*/ if(zmaprow2col2=0) /* mean the way could go at this stage */ len=zfindpath(row2,col2,erow,ecol); if(len>0) pathlen.row=row2; /* use recursion to find the path */ pathlen.col=col2; return +len; return 0;下面这一段，我们将给出对这一段程序的分析： 首先，我们定入了函数int zfindpath(int row,int col,int erow,int ecol) 来进行求解。其中row和 col为传入函数中的入口地址坐标， 而erow 和ecol则是出口地址的坐标。其次，给出了递归程序退出的出口条件：if(row=erow)&&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; 即，如果出口与入口的坐标相同，说明我们已找到终点，可以退出了。如若不然，说明我们还没到达最终目的地，还需继续寻找；如前所述，当前已走过的可行的应设为墙，以防止在程序的搜索过程中，其又按原路返回，造成死循环，即为以下程序所示示：zmaprowcol=2; /* block current position */当然，如果在当前方向下没找到出路，我们将要换向下，用语句row2=row+offsetsdir.row; /* step to next space */ col2=col+offsetsdir.col; /* if want to observe the trace of the ball,you should add code after here!*/来实现我们的目的，其中dir的0，1，2，3值的取向，分别代表了东西南北的搜索过程。如果当前路的下一步为0，说明此路可通，我们深入下一层递归之中，以便找出最终解： if(zmaprow2col2=0) /* mean the way could go at this stage */ len=zfindpath(row2,col2,erow,ecol); 正如前面所述，如果找到终点，则返回一个true 值。此时，len将是大于0的。便将执行以下程序：if(len>0) pathlen.row=row2; /* use recursion to find the path */ pathlen.col=col2; return +len;即告诉我们，已找到合适的路径了，正在记录。这样等这段程序运行完成后，我们合适的路径就在pathlen中保存了。 b.当然，如果仅是这样输出的话，肯定不好看，也不好观察具体中间程序的运行细节，于是我们进行了图行界面的输出以动态显示。 首先，我们要根据地图来创建图形式的迷宫：createmap()函数正是来完成这个工作。 void createmap(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,"c:tc"); cleardevice(); setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); outtextxy(70,20,"hello,welcome to here! "); setcolor(4); setfillstyle(1, 4); for(i=0;i<10;i+) for(j=0;j<10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ line(100,80,150+n2*22,100+n1*22); /* draw a line */ line(337+(n4-8)*22,287+(n3-8)*22,337,360); setcolor(1); settextstyle(4, 0, 3); outtextxy(80,60,"this is the entrance! "); outtextxy(320,360,"this is the exit! ");其中的参数n1,n2,n3,n4并不是产生图形界面所必需的，而仅是做为输出一些字符辅助文字而附加的定义坐标。接下来，我们将对这个函数进行一些细致的分析： 首先，我们应遵循应用图形界面的一些套话：int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,"c:tc");来实现图形模式的初始化。接着，在用setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); 进行了前景色、背景色及填充色的设定后，便可以进行画格子了： for(i=0;i<10;i+) for(j=0;j<10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ 通过这几句话，我们便完成了画格子。其中，设定每个格子宽为20个单位，高为20个单位。具体bar及setfillstyle 及颜色的设定值和其用法，如附录中所示。c. 接下来，如果要动态的显示其过程的话，我们还需要一个小球，setcolor(10); /* draw a cirlce */ setfillstyle(1, 14); circle(150+(col)*22+10,100+(row)*22+10, 8); floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10); 这几句话，我们就画好了一个小球。然后，我们将搜索过程用小球动态的显示，int zfindpath(int row,int col,int erow,int ecol) int dir,row2,col2; /* int x=150+col*22,y=100+row*22; */ sleep(1); setcolor(10); /* draw a cirlce */ setfillstyle(1, 14); circle(150+(col)*22+10,100+(row)*22+10, 8); floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10); 通过一次次的递归调用，其不断的修改传入函数的col和row，即当前坐标，从而不断的画圆，即动态的显示了移运的轨迹。当找不着出路而返回时，又需要擦除已画的圆，我们用setfillstyle(1, 15);bar( 150+col*22,100+row*22,170+col*22,120+row*22);来实现目标。即还原格子原来的颜色。这样我们就实现了其动态的过程。这样，我们就完成了程序。本来也就该结束了，但是考虑到一个更为直观的效果，我们又建立了一个函数void creategraphich(int n1,int n2,int n3,int n4) ，让其再次走完最终路径的全过程.for(i=len;i>0;i-) /* the total number of the path is len */ trow=pathi-1.row-pathi.row; tcol=pathi-1.col-pathi.col; sleep(1); x=x+tcol*22; y=y+trow*22; putimage(x,y, buf, COPY_PUT);putimage函数正好有这一功能。于是，程序这样就结束了。在中途中，我们在移动小球的过程中，用了系统sleep函数来使他暂停。为了更好的显示小球在搜索过程中的动态效果，我们特地设置了两个地图，以资对比；当然，更多的地图也是可以的，但我们只仅仅提供个样例。图5 地图2本程序进行了通俗化处理，以显示任意不同的两点间的搜索路径。并且设置了死循环（while(1)），可以一直输入求解和求解目标。三问题的求解：（程序）a.程序：#include "stdio.h"#include "conio.h" /*provide the support of getch */#define max 10#define maxlength (max*max) /*the max lenth of the path*/#define zdir 4 /*the total direction*/#include "graphics.h" /*provide the support of graphics*/#include "dos.h" /* provide the support of function:sleep */#include "time.h" /* provide the support of sleep */#define M 10 /*the max lenth of the map*/ #define N 10 /*the max lenth of the map*/*the following four function are stating functions*/void printmap(void);int zfindpath(int row,int col,int erow,int ecol);void creategraphich(int n1,int n2,int n3,int n4);void creategraphich(int n1,int n2,int n3,int n4);int zmapmaxmax= 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1 ;struct int row,col; offsetszdir=0,1 , 1,0 , 0,-1, -1,0 ;struct int row; int col; pathmaxlength;/*define a globle variable to convenience output*/int len;int zfindpath(int row,int col,int erow,int ecol) int dir,row2,col2; /* int x=150+col*22,y=100+row*22; */ sleep(1); setcolor(10); /* draw a cirlce */ setfillstyle(1, 14); circle(150+(col)*22+10,100+(row)*22+10, 8); floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10); if(row=erow)&&(col=ecol) path0.row=erow; path0.col=ecol; /* judge if is the exit */ return 1; /* the end of if */ zmaprowcol=2; /* block current position */ for(dir=0;dir<zdir;dir+) row2=row+offsetsdir.row; /* step to next space */ col2=col+offsetsdir.col; if(zmaprow2col2=0) /* mean the way could go at this stage */ len=zfindpath(row2,col2,erow,ecol); if(len>0) pathlen.row=row2; /* use recursion to find the path */ pathlen.col=col2; return +len; /*the end of if */ /*the end of if */ /* the end of for */ sleep(1); setfillstyle(1, 15); bar( 150+col*22,100+row*22,170+col*22,120+row*22); /* sleep(1); */ return 0; /* the end of zfindpaht */void printmap() /* first ,print the map that we will go */ int i,j; for(i=0;i<max;i+) for(j=0;j<max;j+) printf(" %d",zmapij); printf("n"); getch();void createmap(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,"c:tc"); cleardevice(); setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); outtextxy(70,20,"hello,welcome to here! "); setcolor(4); setfillstyle(1, 4); for(i=0;i<10;i+) for(j=0;j<10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ line(100,80,150+n2*22,100+n1*22); /* draw a line */ line(337+(n4-8)*22,287+(n3-8)*22,337,360); setcolor(1); settextstyle(4, 0, 3); outtextxy(80,60,"this is the entrance! "); outtextxy(320,360,"this is the exit! "); void creategraphich(int n1,int n2,int n3,int n4) int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22; void *buf; int gdriver=DETECT,gmode=VGAHI; initgraph(&gdriver,&gmode,"c:tc"); cleardevice(); setbkcolor(10); setcolor(1); settextstyle(4, 0, 5); outtextxy(70,20,"hello,welcome to here! "); setcolor(4); setfillstyle(1, 4); for(i=0;i<10;i+) for(j=0;j<10;j+) if(zmapij=1) setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ else setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/ line(100,80,150+n2*22,100+n1*22); /* draw a line */ line(337+(n4-8)*22,287+(n3-8)*22,337,360); setcolor(1); settextstyle(4, 0, 3); outtextxy(80,60,"this is the entrance! "); outtextxy(320,360,"this is the exit! "); setcolor(4); /* draw a circle heart */ setfillstyle(1, 4); sector(250,350,0,180,20,20); /* draw the upper circle */ sector(290,350,0,180,20,20); /* draw the downer circle */ sector(310,350,180,240,80,76); sector(230,350,300,360,80,76); setcolor(10); /* draw a cirlce */ setfillstyle(1, 14); circle(150+(n2)*22+10,100+(n1)*22+10, 8); floodfill(150+(n2)*22+10+4, 100+(n1)*22+10+4, 10); size=imagesize(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8); buf=malloc(size); getimage(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8,buf); /*sleep(2); putimage(192,122 , buf, COPY_PUT); */ for(i=len;i>0;i-) /* the total number of the path is len-1 */ trow=pathi-1.row-pathi.row; tcol=pathi-1.col-pathi.col; sleep(1); x=x+tcol*22; y=y+trow*22; putimage(x,y, buf, COPY_PUT); /* printf the result*/ setcolor(1); settextstyle(4, 0, 3); outtextxy(357,287,"sussessfully!"); getch(); closegraph(); free(void *)buf); void changemap(int d) FILE *fw; int i,j; if(d=1) fw=fopen("c:tca.txt","r"); if(!fw) printf("not found!"); getch();return; for(i=0;i<M;i+) for( j=0;j<N;j+ ) fscanf(fw,"%d",&zmapij); /* the end of for */ /* the end of first if*/ else fw=fopen("c:tcb.txt","r"); if(!fw) printf("not found!"); getch();return; for(i=0;i<M;i+) for( j=0;j<N;j+ ) fscanf(fw,"%d",&zmapij); /* the end of for */ /* the end of else */ printf("the map we will follow to search :n"); for(i=0;i<M;i+) for(j=0;j<N;j+) printf(" %d",zmapij); printf("n"); getch();fclose(fw); main() while(1) int i,j,n1,n2,n3,n4,n5,n6; int zch; /* while(1) */ len=0; printf("if you want to use the default map,press 1,if you want to use the spare map,press 2 :n"); scanf("%d",&zch); if(zch=2) changemap(1); /*