【算法】老鼠走迷宫问题的解答

一．题目：

用一个m行n列的二维数组来表示迷宫。数组中每个元素的取值为0或1。其中值0表示通路，值1表示阻塞，迷宫的入口在左上放（1，1）处，出口在右下方（m，n）处。要求求出从迷宫入口到出口有无通路，若有通路则指出其中一条通路的路径，即输出找到通路的迷宫数组，其中通路上的“0”用另外一个数字8替换，同时打印出所走通路径上每一步的位置坐标及下一步的方向。

二．算法说明：

（1）以二维数组maze[m][n]表示迷宫，并设maze[1][1]处为迷宫入口，maze[m][n]处为迷宫出口，迷宫中的任一位置以maze[i][j]来表示。

（2）对于迷宫中的每个位置（i，j）处，可能移动的路线可以有八个方向，用一个二维数组move表示这八个方向上坐标的增量，并把这八个方向从正东起按顺时针方向编上序号，则 move[k][0]表示第k个方向上i的增量，

move[k][1]表示第k个方向上j的增量。

move数组的方向增量表内容如下：k 1 2 3 4 5 6 7 8

int move[8][2]={ {0,1}, //正东 i不变 j+1 向右
{1,1}, //右下 i+1 j+1
{1,0}, //下 i+1 j不变
{1,-1}, //
{0,-1}, //
{-1,-1}, //
{-1,0}, //
{-1,1}}; //

（3）当处于迷宫边缘时，它的下一个位置不再有八种可能，甚至只有三种可能。所以，为了简化边界位置的检测，将二维数组maze[m][n]扩充到maze[m+2][n+2]，且令其四周边界位置的值均为1。

（4）计算机解迷宫，要用一步一试探的方法。为此在开始每一步时，都要从正东方向起，沿顺时针方向检测。当探测到某个方向上下一个位置的值为0时，就沿着此方向走一步，当这一步周围剩下的七个方向的上的值均为1时，则退回一步重新检测下一方向。在这过程中，建立一个mark[m+2][n+2]数组来记录某位置是否走过，走过用1记，未走过用0记。据此，可以用递归的思路来解决该问题。

（5）具体的算法可以概括如下：

走迷宫过程中，如果当前位置（i，j）（初始以入口为当前位置）已到达出口，即（i，j）=（m，n），则说明已找到一条通路，返回值1，表示走通，结束递归过程；

如果当前位置的各个方向上都没有找到通向出口的路径，则递归返回值0，表示未走通，若此时的位置在入口处，给出“没有通路”的信息，结束递归；

如果对当前位置的各个方向依次试探的过程中，发现某个方向的试探位置可以走（即maze与mark数组中该位置的值均为0），则把试探位置作为调用参数递归调用走迷宫过程，同时对调用的返回值进行判断，若调用返回值为1，则表示当前位置在走通的路径上，因此要记录下该位置，且递归返回1。

在记录走通的每步位置时，考虑到递归的特点，若要正序打出走通的路径，我们则可以另入口和出口颠倒，即可实现目的。

三，源码

#include <iostream>using namespace std;const int  m=12,n=15;//迷宫的大小int maze[m+2][n+2]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,//输入迷宫地图                    1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,                    1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,                    1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,                    1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,                    1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,                    1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,                    1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,                    1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,                    1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,                    1,1,1,0,0,0,1,1,0,1,1,0,0,0,1,0,1,                    1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,                    1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,                    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};int mark[m+2][n+2];//设立迷宫是否走过标志int move[8][2]={{0,1},    //正东   i不变   j+1  向右                  {1,1},    //右下    i+1   j+1                  {1,0},    //下  i+1  j不变 {1,-1},   //{0,-1},   //{-1,-1},  //{-1,0},   //{-1,1}};  ////方向指标int SeekPath(int x,int y){    int i,g,h;    if(x==1&&y==1) //如果到终点则找到路径,返回 1return 1;    for (i=0;i<8;i++)//尝试每一个方向     {       g=x+move[i][0];       h=y+move[i][1]; //探索地点的新坐标               if(maze[g][h]==0&&mark[g][h]==0)//如果该地点走得通且没有被探索过       {           mark[g][h]=1;//将这一地点置为探索过            if(SeekPath(g,h))//从这一地点开始新的探索,如果成功           {              cout<<"("<<g<<","<<h<<")";//则打出这一点的坐标              if(move[i][0]==1) cout<<"North->";              if(move[i][0]==-1) cout<<"South->";              if(move[i][1]==1) cout<<"West->";              if(move[i][1]==-1) cout<<"East->";//判断前一地点到这一地点的方向              cout<<endl;              maze[g][h]=8;//把这一点设为通路               return 1;//返回1            }       }    }    if(x==m&&y==n)     cout<<"No path!"<<endl;//如果最后回到了起点,则说明没有通路     return 0;//返回0} int main(){    int i,j;    for (i=0;i<m+2;i++)       for (j=0;j<n+2;j++)           mark[i][j]=0;//先将所有通路置为没有走过               mark[m][n]=1;//将起点置为走过了    if(SeekPath(m,n)) //如果走通     {       cout<<"("<<m<<","<<n<<")"<<endl;//先打出起点坐标       maze[m][n]=8;//将起点设为通路       for (i=0;i<m+2;i++)           for (j=0;j<n+2;j++)           {              cout<<maze[i][j]<<" ";              if(j==n+1)   cout<<endl;           }//打印出走通后的迷宫    }}

1楼xuhuan1108前天 00:35

我运行了一下发现每一个有move的地方(除了定义处)都产生了error:“move”: 不明确的符号错误！n敢问这是什么编辑器啊？还有能不能推荐一个好的编辑器啊！n谢谢！

Re: tianshuai11昨天 21:41

回复xuhuan1108n我用的是CFree 5.0 我确实遇到过移植编译出错问题！！！O(∩_∩)O~