C++迷宫求解详解--栈_C/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

• maze.zip (1.5 KB)
• 描述: 代码实现
• 下载次数: 0