首页 > 代码库 > 迷宫问题

迷宫问题

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 
假设迷宫如下图所示: 
# # # # # # # # # # 
# & & # $ $ $ # # 
# & # $ $ $ # # 
# & $ $ # # # 
# & # # # # # 
# & & & # # # 
# # & & & # # 
# # # # # & # # # 
# & & & Q # 
# # # # # # # # # # 

    假设“当前位置”指的是“在搜索过程中某一 
时刻所在图中某个方块位置”,则求迷宫中一条路 
径的算法的基本思想是:若当前位置"可通",则纳 
入"当前路径",并继续朝“下一位置”探索,即切 
换“下一位置”为“当前位置”,如此重复直至到 
达出口;若当前位置“不可通”,则应顺着“来向” 
退回到“前一通道块”,然后朝着除“来向”之外的其他方向继续探索;若该通道块的四周四个方块均“不可通”,则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向(东、南、西、北)上相邻的方块。假设以栈S记录“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作即为“当前位置入栈”;“从当前路径上删除前一通道块”的操作即为“出栈”。 
    求迷宫中一条从入口到出口的路径的算法可简单描述如下: 

    设定当前位置的初值为入口位置; 
do{ 
   若当前位置可通, 
   则{将当前位置插入栈顶;    // 纳入路径 
       若该位置是出口位置,则结束;             
                            // 求得路径存放在栈中 
       否则切换当前位置的东邻方块为新的当前位置; 
      } 
   否则 { 
     若栈不空且栈顶位置尚有其他方向未被探索, 
     则设定新的当前位置为: 沿顺时针方向旋转 
                     找到的栈顶位置的下一相邻块;               
     若栈不空但栈顶位置的四周均不可通, 
     则{  删去栈顶位置;  // 从路径中删去该通道块                   
           若栈不空,则重新测试新的栈顶位置, 
           直至找到一个可通的相邻块或出栈至栈空; 
        } 
}while (栈不空); 

    在此,尚需说明一点的是,所谓当前位置可通,指的是未曾走到过的通道块,即要求该方块位置不仅是通道块,而且既不在当前路径上(否则所求路径就不是简单路径),也不是曾经纳入过路径后又从路径上删除的通道块(否则只能在死胡同内转圈)。 

    typedef struct { 
      int ord;            // 通道块在路径上的“序号” 
      PosType seat;   // 通道块在迷宫中的“坐标位置” 
      int di;   // 从此通道块走向下一通道块的“方向” 
    } SElemType;          // 栈的元素类型 

Status MazePath ( MazeType maze, PosType start, 
                                   PosType end ) { 
  // 若迷宫maze中从入口 start到出口 end的通道, 
  // 则求得一条存放在栈中(从栈底到栈顶),并返回 
  //  TRUE;否则返回FALSE 
  InitStack(S);  curpos = start; 
                // 设定“当前位置”为“入口位置” 
  curstep = 1;                       // 探索第一步 
  do { 
if (Pass (curpos)) { 
   // 当前位置可以通过,即是未曾走到过的通道块 
      FootPrint (curpos);              // 留下足迹 
      e = ( curstep, curpos, 1 ); 
      Push (S,e);                    // 加入路径 
      if ( curpos == end )  return (TRUE); 
                             // 到达终点(出口) 
      curpos = NextPos ( curpos, 1 ); 
                       / 下一位置是当前位置的东邻 
      curstep++;                      // 探索下一步 
    } 
    else {  // 当前位置不能通过 
      if (!StackEmpty(S)) { 
        Pop (S,e); 
        while (e.di==4 && !StackEmpty(S)) { 
           MarkPrint (e.seat);  Pop (S,e);     
                 // 留下不能通过的标记,并退回一步 
           } // while 
           if (e.di<4) { 
             e.di++;   Push ( S, e); 
                              // 换下一个方向探索 
             curpos = NextPos (curpos, e.di );   
              // 设定当前位置是该新方向上的相邻块 
           } // if 
         } // if 
       } // else 
   } while ( !StackEmpty(S) ); 
   return (FALSE); 
} // MazePath 

 

程序完整代码:

 1 #include <iostream>       2 #include <iomanip>   3 #include <stdlib.h> 4 using namespace std;  5  6  7 #define MaxSize 100 8  9 int mg[10][10] = {      //定义一个迷宫,0表示通道,1表示墙10     {1,1,1,1,1,1,1,1,1,1},11     {1,0,0,1,1,0,0,1,0,1},12     {1,0,0,1,0,0,0,1,0,1},13     {1,0,0,0,0,1,1,0,0,1},14     {1,0,1,1,1,0,0,0,0,1},15     {1,0,0,0,1,0,0,0,0,1},16     {1,0,1,0,0,0,1,0,0,1},17     {1,0,1,1,1,0,1,1,0,1},18     {1,1,0,0,0,0,0,0,0,1},19     {1,1,1,1,1,1,1,1,1,1}};20 21 struct St                //定义一个栈,保存路径22 {23     int i;               //当前方块的行号24     int j;               //当前广场的列号25     int di;              //di是下一可走方位的方位号26 } St[MaxSize];           //定义栈27 28 int top = -1;            //初始化栈指针29 30 void MgPath(int xi, int yi, int xe, int ye)            //路径为从(xi,yi)到(xe,ye)31 {32     int i, j, di, find, k;33     top++;                                             //初始方块进栈34     St[top].i = xi;St[top].j = yi;St[top].di = -1;35     mg[xi][yi] = -1;36     while(top>-1)                                      //栈不为空时循环37     {38         i = St[top].i;j = St[top].j;di = St[top].di;39         if(i==xe && j==ye)                             //找到了出口,输出路径40         {41             cout << "迷宫路径如下:\n";42             for(k=0; k<=top; k++)43             {44                 cout << "\t(" << St[k].i << "," << St[k].j << ")";45                 if((k+1)%5==0) cout << endl;            //每输出五个方块后换一行46             }47             cout << endl;48             return;49         }50         find = 0;51         while(di<4 && find==0)                          //找下一个可走方块52         {53             di++;54             switch(di)55             {56             case 0:i = St[top].i-1; j = St[top].j; break;57             case 1:i = St[top].i; j = St[top].j+1; break;58             case 2:i = St[top].i+1; j = St[top].j; break;59             case 3:i = St[top].i; j = St[top].j-1; break;60             }61             if(mg[i][j]==0) find = 1;                      //找到通路62         }63         if(find==1)                                        //找到了下一个可走方块64         {65             St[top].di = di;                               //修改原栈顶元素的di值66             top++;                                         //下一个可走方块进栈67             St[top].i = i; St[top].j = j; St[top].di = -1;68             mg[i][j] = -1;                                 //避免重复走到这个方块69         }70         else                                               //没有路可走,则退栈71         {72             mg[St[top].i][St[top].j] = 0;                  //让该位置变成其它路径可走方块73             top--;74         }75     }76     cout << "没有可走路径!\n";77 }78 79 int main()80 {81     MgPath(1,1,8,8);82 }
View Code

 

迷宫问题