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

迷宫问题求解 一问题的提出： 人类建造迷宫已有5000年的历史。在世界的不同文化发展时期，这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走，寻找真相。关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是rpg玩多了）。这则神话讲的是，从前弥诺斯王统治着克里特岛。有一年，他没有给海神波塞冬送去允诺的祭物公牛，海神十分生气，决意报复。他附体在公牛身上，勾引了弥诺斯王的妻子帕西法厄王后。不久，王后生下一个牛首人身的怪物弥诺陶洛斯(minotaur)。为了把怪物藏起来避免家丑外扬，弥诺斯王命令岛上最优秀的工匠代达罗斯造了一座迷宫：一所稀奇古怪的地下房子，走廊离亮处越来越远，根本找不到出口。发狂的弥诺陶洛斯在一堵堵墙壁之间徘徊游荡，左突右冲，以雅典王进贡的童男童女充饥。终于有一天，雅典王子忒修斯(theseus)带着宝剑冒充进贡的童男进入迷宫。他一路退下弥诺斯王的女儿阿里阿德涅送给他的线团的线，杀死了牛头怪物弥诺陶洛斯，又沿着这根线找到出口，活着离开迷宫.一般的迷宫为二维平面图形,将迷宫的左上角作入口，右下角作出口，求出从入口点到出口点的一条通路。迷宫的大小为nn，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;dir0) 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(len0) 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;i10;i+) for(j=0;j10;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;i10;i+) for(j=0;j0;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;dir0) 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;imax;i+) for(j=0;jmax;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;i10;i+) for(j=0;j10;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;i10;i+) for(j=0;j0;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;im;i+) for( j=0;jn;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;im;i+) for( j=0;jn;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;im;i+) for(j=0;j0;i-) printf(%d,%d)n,pathi.row,pathi.col); /* the end of for*/ getch();printf(now,we will create the final graphics of the map:n); /* create the final graphics of the map*/ getch(); creategraphich(n5,n6,n3,n4); /* the end of while */ /* the end of main */b.图例： 图6 首先，让我们选择地图 图7 然后，输出我们选择的地图 图8 按着输入我们的入口坐标和出口坐标（1，1），（8，8）（当然可以任意输入，这只是做为一个样例） 接下来将动态搜索，由于这时截不到图，只能将动态运行找到的合适路径输出。 图9 动态运行找到的合适路径输出按着又进行最终输出，之后是住而复始。c程序中用到的变量、函数说明： max 地图的长或宽的长度。 int zmapmaxmax 用以存放地图的数组。offsetszdir 用以存放方向的结构体数组。pathmaxlength 用以存放路径的数组。row,col 分别是起点的坐标。erow,ecol 分别是终点的坐标。row2,col2是搜索中的探索性坐标。a.txt，和b.txt 是地图。 void printmap(void) ：输出地图。int zfindpath(int row,int col,int erow,int ecol)：寻找路径。void creategraphich(int n1,int n2,int n3,int n4)：输出最终效果图。 void createmap(int n1,int n2,int n3,int n4):产生图形化界面。 其它未提到的在程序中将有注释。四问题的结果分析：比起堆栈类来说，使用递归算法的类要简短地多，这也说明了递归程序的好处：简洁清晰、可读性强。而且结果也是令我们满意和信服的。当然程序也有许多要改进的地方，期望能得到老师和同学们的指正。简洁和高效永远是编程人员应当追寻的准则。五附录：1.设置前景色 setcolor(int c); 用法： setcolor(i); /c为整型变量，范围是015,代表16种颜色，setbkcolor(int c) :设置图形屏幕的背景色彩，使用该函数后图形屏幕清屏，背景色彩为该函数中所指定的色彩。如果没有使用该函数设置背景色，则图形屏幕的背景色彩为黑色。依次是 0-black 黑 1-blue 深蓝 2-green 暗绿 3-cyan 青 4-red 暗红 5-magenta 暗紫 6-brown 棕 7-lightgray 灰 8-darkgray 暗灰 9-lightblue 蓝 10-lightgreen 绿 11-lightcyan 青 12-lightred 红 13-lightmagenta 紫 14-yellow 黄 15-white 白2.画实心矩形 bar(x1,y1,x2,y2); 用法： bar(x1,y1,x2,y2);/作用是画一条左上角在(x1,y1)右下角在(x2,y2)的实心矩形，由setfil