C++迷宫求解详解--栈

         相信大家都应该听过栈吧，一直想利用栈来实现一个算法，最近有点空，就利用栈的先进后出的特性来完成迷宫求的问题，下面将详细介绍栈的实现和迷宫求解的过程，可以很好的学习栈的使用。

 

      栈有两种实现方法，一种是顺序，即数组形式，一种是线性，即链表形式，个人还是比较喜欢链表形式实现栈的基本功能。

 

  首先弄一个简单的迷宫，如图：

 我们很容易看出这个迷宫解的路径，那怎么让计算机帮我们求解出来呢。

首先我们要对迷宫数据化，很容易想到二维数组来表示，0表示通路，1表示障碍，即表示为：

int map[4][4]={
        {0,1,1,0},
        {0,0,0,0},
        {0,0,1,1},
        {1,0,0,0}
    };

我们的思路是，从入口出发，顺着探索方向向前探索，如能走通，则继续往前走；否则，沿原路退回，换一个方向进行探索，直至试探出口为止。看到这个思路，发现使用栈是多么的合适。下面我们就来实现迷宫解答。

 

一.栈的实现

我们首先要会实现栈的出栈入栈等基本栈的构建

定义栈的结构：

struct node
{
    int x;//行
    int y;//列  对应map[x][y]
    int direction;//1代表向右，2代表向下，3代表向左，4代表向上，存放探索方向,下一次探索的方向
    node *next;
    int above;//上一块是哪个方向探索下来的，防止左右上下死循环
    node()
    {
        next=NULL;
    }
};

 

定义栈的头指针：node *head=NULL;

 

数据入栈函数：

//进栈---插入到head之后
void Push(node * &head,int x,int y,int direction,int above)
{
   
     node * temp=new node;
     temp->x=x;temp->y=y;temp->direction=direction;
     temp->above=above;

     if(head==NULL)
         head=temp;
     else
     {
         temp->next=head;
         head=temp;
     }

}
数据出栈实现：

//出栈--取head后
void Pop(node * &head)
{
    node * ok;
    if(head!=NULL)
    {
       
        ok=head;
        head=head->next;
        delete ok;
    }
      
}

上面就实现了栈的基本功能。下面我们就可以开始对迷宫进行求解了。求实，理解了原理，代码编写就不是难事了。

迷宫求解步骤如下：

首先把入口进栈：Push(head,0,0,1,0);//入口进栈

 

具体探索代码：

//探索路径
    while(true)
    {
        if(Getpop(head).x==3&&Getpop(head).y==3)//找到出口，停止循环
            break;
        //对下一块进行探测
        bool sea=true;
        node  temp;

        //每一步路径探索
        while(sea)
        {
            temp=Getpop(head);       
            //temp.above!=4条件防止左右或上下循环走
            //temp.direction为前进方向
            switch (temp.direction)
            {
            case 1:
                //探索成功，即向右可以，且上一步来的方向不是左，防止左右死循环，探索成功，方向加一，便于下次回溯换一个方向探索
                if((temp.y+1)<BLOCKNUM&&map[temp.x][temp.y+1]==0&&temp.above!=3)
                {
                    Change(head,temp.direction+1);   
                    Push(head,temp.x,temp.y+1,1,1);//探索成功进栈
                    sea=false; //停止循环
                   
                }
                else
                {
                    Change(head,temp.direction+1);        //向右探索失败，探索方向加一，继续探索
                }
           
                break;
            case 2:
                if((temp.x+1)<BLOCKNUM&&map[temp.x+1][temp.y]==0&&temp.above!=4)
                {
                    Change(head,temp.direction+1);
                    Push(head,temp.x+1,temp.y,1,2);
                    sea=false;
                }
                else
                {
                    Change(head,temp.direction+1);
                }
                break;
            case 3:
                if((temp.y-1)>=0&&map[temp.x][temp.y-1]==0&&temp.above!=1)
                {
                    Change(head,temp.direction+1);
                    Push(head,temp.x,temp.y-1,1,3);
                    sea=false;
                }
                else
                {
                    Change(head,temp.direction+1);
                }
                break;
            case 4:
                if((temp.x-1)>=0&&map[temp.x-1][temp.y]==0&&temp.above!=2)
                {
                    Change(head,temp.direction+1);
                    Push(head,temp.x-1,temp.y,1,4);
                    sea=false;
                }
                else
                {
                    Pop(head);
                    sea=false;
                }
                break;
            default://即当temp.direction==5，此方块已经把所有方向都探索完了，把他出栈
                Pop(head);
                sea=false;
                break;
            }
        }
       
    }

通过上面两个while循环即可实现了迷宫求解。

 

主要要注意避免探索过程中出现左右或上下来回探索，实现了死循环

附加上代码下载地址：

完整代码下载地址：https://github.com/longpo/algorithm/tree/master/maze