`
mmdev
  • 浏览: 12845088 次
  • 性别: Icon_minigender_1
  • 来自: 大连
文章分类
社区版块
存档分类
最新评论

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

 
阅读更多

一.题目:

用一个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) //如果到终点则找到路径,返回 1
		return 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;
           }//打印出走通后的迷宫
    }
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics