用栈求解迷宫问题

                             求解迷宫问题

---

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

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

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

• 为了表示迷宫,设置一个数组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("该迷宫问题没有解!");
}