首页 > 代码库 > 转载:迷宫求解

转载:迷宫求解

迷宫求解----递归实现  

2010-01-14 14:02:28|  分类: 算法及分析|举报|字号 订阅

 
 

 一、问题的分析:

技术分享技术分享

本问题的求解,关键是如何找到求解任意两个点间,按照以上基本思想而走出的路线。按照这个路线,我们可以通过图形函数来动态的显示迷宫的搜索过程。

计算机解迷宫解通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进,否则沿着原路退回,换一个方向继续探索,直至出后位置,求得一条通路。假如所有可能的通路都探索到位能到达出口,则所设定的迷宫没有通路。

为此,我们先要处理地图问题。将地图中有墙的地方设为1,而没墙的地方,也即可以通行的地方设为0,如:在我们的这个程序中的一个例子中,地图如下显示:

技术分享

   当然了,有了地图,下一步就是如何在地图中查询可行路线了。按照基本思想,当前已走过的可行的应设为墙,以防止在程序的搜索过程中,其又按原路返回,造成死循环。在我们的程序中,我们设走过的路的地图所在地为2,如下示:

zmap[row][col]=2;             /* block current position */

      搜索路线,当需要一个数组来存储可行路线了,我们在程序中如下设定:struct {

    int row;           /* the row of the position */

    int col;           /* the col of the position */

} path[maxlength];

由基本思想,搜索中按东南西北的先后顺序,我们又定义一个结构体来进行搜索中的换向,如下示:

struct {

       int row,col;

      }offsets[zdir]={ {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))

    { path[0].row=erow;

      path[0].col=ecol;    /* judge if is the exit出口*/

      return 1;

        }

      zmap[row][col]=2;             /* block current position */

       for(dir=0;dir<=zdir;dir++)

        {

          row2=row+offsets[dir].row;  /* step to next space */

          col2=col+offsets[dir].col;  /* if want to observe the trace of the ball,you should add code after here!*/

          if(zmap[row2][col2]==0)      /* mean the way could go at this stage */

            {  len=zfindpath(row2,col2,erow,ecol);

               if(len>0)

                 {

                   path[len].row=row2;      /* use recursion to find the path  */

                   path[len].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))

    {

  path[0].row=erow;

      path[0].col=ecol;    /* judge if is the exit */

      return 1;

     }

即,如果出口与入口的坐标相同,说明我们已找到终点,可以退出了。如若不然,说明我们还没到达最终目的地,还需继续寻找;如前所述,当前已走过的可行的应设为墙,以防止在程序的搜索过程中,其又按原路返回,造成死循环,即为以下程序所示示:

zmap[row][col]=2;             /* block current position */

当然,如果在当前方向下没找到出路,我们将要换向下,用语句

row2=row+offsets[dir].row;  /* step to next space */

col2=col+offsets[dir].col;  /* if want to observe the trace of the ball,you should add code after here!*/

来实现我们的目的,其中dir的0,1,2,3值的取向,分别代表了东西南北的搜索过程。如果当前路的下一步为0,说明此路可通,我们深入下一层递归之中,以便找出最终解:

    if(zmap[row2][col2]==0)      /* mean the way could go at this stage */

  len=zfindpath(row2,col2,erow,ecol);

   正如前面所述,如果找到终点,则返回一个true 值。此时,len将是大于0的。便将执行以下程序:

if(len>0)  

{

                  path[len].row=row2;      /* use recursion to find the path  */

                   path[len].col=col2;

                   return ++len;

}

即告诉我们,已找到合适的路径了,正在记录。这样等这段程序运行完成后,我们合适的路径就在path[len]中保存了。

 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(zmap[i][j]==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(zmap[i][j]==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=path[i-1].row-path[i].row;

      tcol=path[i-1].col-path[i].col;

      sleep(1);

      x=x+tcol*22;

      y=y+trow*22;

      putimage(x,y, buf, COPY_PUT);

putimage函数正好有这一功能。

于是,程序这样就结束了。

在中途中,我们在移动小球的过程中,用了系统sleep函数来使他暂停。

为了更好的显示小球在搜索过程中的动态效果,我们特地设置了两个地图,以资对比;当然,更多的地图也是可以的,但我们只仅仅提供个样例。

技术分享

本程序进行了通俗化处理,以显示任意不同的两点间的搜索路径。并且设置了死循环(while(1)),可以一直输入求解和求解目标。

二、C语言实现问题的求解:(递归)

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 zmap[max][max]={ {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;

       }offsets[zdir]={{0,1 },

                       {1,0 },

                       {0,-1},

                       {-1,0}

                       };

struct {

    int row;

    int col;

    } path[maxlength];

/*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))

    { path[0].row=erow;

      path[0].col=ecol;    /* judge if is the exit */

      return 1;

        }   /* the end of if */

      zmap[row][col]=2;             /* block current position */

       for(dir=0;dir<zdir;dir++)

        {

          row2=row+offsets[dir].row;  /* step to next space */

          col2=col+offsets[dir].col;

          if(zmap[row2][col2]==0)      /* mean the way could go at this stage */

            {

 

                len=zfindpath(row2,col2,erow,ecol);

               if(len>0)

                 {

                   path[len].row=row2;      /* use recursion to find the path  */

                   path[len].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",zmap[i][j]);

      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(zmap[i][j]==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(zmap[i][j]==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=path[i-1].row-path[i].row;

      tcol=path[i-1].col-path[i].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:\\tc\\a.txt","r");

     if(!fw) {printf("not found!"); getch();return;}

     for(i=0;i<M;i++)

       {   for( j=0;j<N;j++ )   { fscanf(fw,"%d",&zmap[i][j]);}

 

       }  /* the end of for */

     }/* the end of first if*/

    else  {

     fw=fopen("c:\\tc\\b.txt","r");

     if(!fw) {printf("not found!"); getch();return;}

     for(i=0;i<M;i++)

       {   for( j=0;j<N;j++ )   { fscanf(fw,"%d",&zmap[i][j]);}

 

       }  /* 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",zmap[i][j]);}

          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);

        /*printmap(); */

      else

        {

         changemap(2);

         /* printmap();  */                       /* first ,print the map that we will go */

        }

     printf("please input the startpoint(row,col):\n"); /* input the start point and end point ,those two value should less then 10 and larger then 0*/

      scanf("%d%d",&n1,&n2);

      printf("please input the endpoint(row,col):\n");

      scanf("%d%d",&n3,&n4);

      n5=n1;

      n6=n2;

      createmap(n5,n6,n3,n4);    /* in this step ,we will create the primitive map */

      zfindpath(n1,n2,n3,n4);             /* function of searching the path */

      path[len].row=n5;

      path[len].col=n6;

      getch();

      closegraph();

    printf("the resultant path is \n");

    for(i=len;i>0;i--)

  {

      printf("(%d,%d)\n",path[i].row,path[i].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 zmap[max][max] 用以存放地图的数组。

offsets[zdir]  用以存放方向的结构体数组。

path[maxlength] 用以存放路径的数组。

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为整型变量,范围是0~15,代表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)的实心矩形,由setfillstyle设置填充方式。

3.设置填充方式 setfillstyle();

用法:

setfillstyle(p,c);//p一般取1(实心),c为填充的颜色( 0~15 )

outtextxy(x,y,"Strings");//在(x,y)处打印"String",用前景色。

4. line(x1,y1,x2,y2):

绘制直线段,其中(x1,y1)为一个端点的坐标,(x2,y2)为另一个端点的坐标。直线的色彩为在使用该函数之前通过setcolor函数所设置的色彩.

5. circle(x,y,r):

绘制一个以(x,y)为圆心坐标,半径为r的圆。

6. closegraph():

关闭图形工作方式,返回到字符工作方式。调用此函数后,屏幕上已经绘制的图形将会被清除。

7. sector(x,y,startangle,endangle,xradius,yradius):

绘制一个扇形。扇形的圆心位置为(x,y),startangle为开始角度,endangle为终止角度,xradius为扇形横半径,yradius为扇形纵半径。注意:这个函数使用的是角度值,而不是弧度值.

8. void far floodfill(int x, int y, int border);
    其中: x, y为封闭图形内的任意一点。border为边界的颜色, 也就是封闭图形轮廓的颜色。调用了该函数后, 将用规定的颜色和图模填满整个封闭图形。

9. void far getimage(int xl,int yl, int x2,int y2, void far *mapbuf);
     void far putimge(int x,int,y,void * mapbuf, int op);
     unsined far imagesize(int xl,int yl,int x2,int y2);
     这三个函数用于将屏幕上的图像复制到内存,然后再将内存中的图像送回到
屏幕上。首先通过函数imagesize()测试要保存左上角为(xl,yl), 右上角为(x2,
y2)的图形屏幕区域内的全部内容需多少个字节, 然后再给mapbuf 分配一个所测数字节内存空间的指针。通过调用getimage()函数就可将该区域内的图像保存在内存中, 需要时可用putimage()函数将该图像输出到左上角为点(x, y)的位置上,
其中getimage()函数中的参数op规定如何释放内存中图像。
10.函数名: sleep 
  能: 执行挂起一段时间 
  法: unsigned sleep(unsigned seconds);

11.说明:这些函数是在网上搜索的。

四、堆栈的C语言描述

技术分享

技术分享技术分享

 

转载:迷宫求解