【算法】老鼠走迷宫问题的解答
一．题目：
用一个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 向右（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; }//打印出走通后的迷宫 }}