欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用栈求解迷宫问题

程序员文章站 2022-06-03 15:52:03
...
                             求解迷宫问题

  • 问题描述
    求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

  • 数据组织
    用如下图的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

  • 所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

用栈求解迷宫问题

  • 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.6所示的迷宫,对应的迷宫数组mg如下:
    int mg[M+2][N+2]={ //M=8,N=8
    {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}};

  • 算法设计
    对于迷宫中的每个方块,有上下左右四个方块相邻,如下图所示,第i行第j列的当前方块的位置为(i,j),规定上方方块为方位0,顺时针方向递增编号。
      在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。

  • 为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中,为此将栈定义为:
typedef struct
{  int i;       //当前方块的行号
   int j;       //当前方块的列号
   int di;      //di是下一可走相邻方位的方位号
} Box;      //定义方块类型
typedef struct
{  Box data[MaxSize];
   int top;     //栈顶指针
} StType;       //顺序栈类型
  • 求解迷宫路径的过程如下:
    用栈求解迷宫问题

  • 代码:

bool mgpath(int xi,int yi,int xe,int ye)    
//求解路径为:(xi,yi)->(xe,ye)
{  int i,j,k,di,find;
   StType st;           //定义栈st
   st.top=-1;           //初始化栈顶指针
   st.top++;            //初始方块进栈
   st.data[st.top].i=xi; st.data[st.top].j=yi;
   st.data[st.top].di=-1; mg[xi][yi]=-1; 
   while (st.top>-1)        //栈不空时循环
   {    i=st.data[st.top].i;j=st.data[st.top].j;
    di=st.data[st.top].di;  //取栈顶方块
    if (i==xe && j==ye) //找到了出口,输出路径
    {   printf("迷宫路径如下:\n");
        for (k=0;k<=st.top;k++)
        {  printf("\t(%d,%d)",st.data[k].i,st.data[k].j);
         if ((k+1)%5==0)    //每输出每5个方块后换一行
            printf("\n");
        }
        printf("\n");
        return true;        //找到一条路径后返回true
    }
       find=0;
   while (di<4 && find==0)  //找下一个可走方块
   {  di++;
      switch(di)
      {
      case 0:i=st.data[st.top].i-1;j=st.data[st.top].j;
             break;
    case 1:i=st.data[st.top].i;j=st.data[st.top].j+1;
             break;
    case 2:i=st.data[st.top].i+1;j=st.data[st.top].j;
             break;
    case 3:i=st.data[st.top].i,j=st.data[st.top].j-1;
             break;
    }
    if (mg[i][j]==0) find=1; //找到下一个可走相邻方块
   }
  if (find==1)           //找到了下一个可走方块
  {  st.data[st.top].di=di;  //修改原栈顶元素的di值
     st.top++;           //下一个可走方块进栈
     st.data[st.top].i=i; st.data[st.top].j=j;
     st.data[st.top].di=-1;
     mg[i][j]=-1;   //避免重复走到该方块
  }
  else      //没有路径可走,则退栈
  { mg[st.data[st.top].i][st.data[st.top].j]=0;
           //让该位置变为其他路径可走方块
    st.top--;   //将该方块退栈
   }
 }
 return false;  //表示没有可走路径,返回false
}


  • 建立如下主函数调用上述算法:
void main()
{  if (!mgpath(1,1,M,N))
    printf("该迷宫问题没有解!");
}