实现简单迷宫是栈的基本操作之一，但对小白们来说也是一个不小的挑战，看到网上大多是只贴出代码，本文将深入的分析这个问题，以模块化的方式展示出来，简单易懂，笔者水平有限，希望大家能点赞过后留下宝贵意见。
利用栈去实现迷宫，首先当我们第一次看到这个问题时，我们可能会想，如何才能用栈去实现呢？还有没有其他操作呢？
（1) 首先我们不妨去设可以去走的格子值为1，已走过的格子值为2，已走过而又再返回的格子为3（这个没有清楚没关系的，我们在后面会解释）我们的思路就是首先得到我们现在位置所处的坐标，分别去检测所处位置的下边，左边，右边和上边，若其为1，则证明其是可以走的，为2则证明其是已经走过的路，除非是回溯（想想看，当我们一条路走到底发现并没有走到出口时，是不是要再沿原路返回，也就是去回溯），否则也是不可以走的，而3是我们回溯后去标记的值，它在所有情况下都是不可以走的，因为这条路已经走过了！而且没有出口！不然干嘛要回溯呢！第一阶段已经完成，我们知道了我们下一步该怎么走。
（2) 我们知道了我们下一步的动作，我们当然要去迈出那一步喽，但是在这之前，我们需要将我们现在所在位置上的值赋为2，代表我们已经走过这个位置。这个时候你可能心里有了疑问，当我一条路走到底发现不是出口的时候怎么办呢？我们来想想栈的特点，没错，先进后出，当我们一条路走到黑发现，诶，不对，这不是出口，我们接下来会做什么，当然是回到上一步，这不就是栈的特点先进后出吗！也就是说我们每走一步，把我们所在的位置信息入栈，当我们需要去回溯时去出栈，所得到的便是我们需要的位置，再把得到的这个位置重复第一步，我们就可以得到下一步，在第一步中我们说过3这个数字，现在应该懂了吧。
（3）别忘了每走一步我们都要去判断这个位置是否为出口。
以上三步就是我们去走每一步的过程，循环下来，就实现了迷宫问题，其中一些细节我们通过模块化的思想将其拆分成以下一些函数块：
- 定义一个记录位置信息的结构体 Point
- 定义一个记录迷宫整体的结构体（主要是为了美观和方便） Warehouse
- 定义一个栈 包含出栈 入栈和创建栈的操作（顺序栈便可实现）
- 定义一个函数 其可以返回下一步要走的值 还可以“智能”进行出栈操作 direc()
- 定义一个函数用来修改当前位置的值 Mark()
- 定义一个判断当前位置是否为出口位置的函数 Isexit()
（1）
//记录位置的结构体
typedef struct
{
int row;//行
int col;//列
}Point;
（2）
//记录迷宫整体的结构体
typedef struct
{
int map[ROW][COL];
}Warehouse;
（3）栈的一系列操作
//栈的结构体
typedef struct
{
int top= -1;
Point shuzu[maxsize]; //这里用一个结构体类型的数组
}track;
//入栈操作
int push_track(track *ptrack,Point pPoint)
{
if(ptrack->top==maxsize-1) return 0;
else{
ptrack->shuzu[(ptrack->top)+=2]=pPoint;/*关于这个地方为什么加2 因为在下面函数中我们出一次栈会自身减2 所以我们
使其入栈时加2 下面会说这个问题 */
return 1;
}
}
//出栈操作
int pop_track(track *ptrack)//第一次写了参数区存储出栈的值 但其实没有什么必要 我们不需要那个值
{
if(ptrack->top==-1) return 0;
else{
ptrack->shuzu[ptrack->top--];
return 0;
}
}
//创建一个栈
track *create()
{
track *s;
s=(track*)malloc(sizeof(track));
s->top=-1;
return s;
}
（4）这是一个神奇的函数 它可以返回我们下一步的的位置，而且会在回溯的时候自动出栈
我们使用了一个Point类型的数组 里面记录了四个对现在位置来说其他四个方向的值
int back(Warehouse *house,Point cur)
{
direc[0]=direc[1]=direc[2]=direc[3]=cur;
direc[0].col++; //temp[0]测试右边
direc[1].row++; //temp[1]测试上面
direc[2].col--; //temp[2]测试左边
direc[3].row--; //temp[3]测试下面
for(int i=0;i<4;i++)
if(house->map[direc[i].row][direc[i].col]==1)
return i;
for(int i=0;i<4;i++)
{
if(house->map[direc[i].row][direc[i].col]==2) //返回我们下一步需要的位置
{
if(house->map[cur.row][cur.col]==2) house->map[cur.row][cur.col]=3;
pop_track(temp); //如果下一步会走到已走到的位置 在返回时出栈
return i;
}
} //这样做使得见到1的优先级高于2 很麻烦 才疏学浅 希望有好的想法可以提出
}
（5）Mark() 修改当前位置的值
void Mark(Warehouse *house,Point cur)
{
if(house==NULL) return;
//对于可落脚点标记为 2
house->map[cur.row][cur.col]=2;
return;
}
（6）判断当前位置是否为出口
int Isexit(Point cur,Point exit)
{
if(cur.row==exit.row&&cur.col==exit.col)
return 1;
return 0; //是出口返回 1 不是则返回 0
}
（7）
我们直接将寻找过程封装进函数。
//找到终点的函数
void pathstack(Warehouse *house,Point entry,Point exit)
{
int number;
if(house==NULL) return; //当地地图没有赋初值时为NULL
Mark(house,entry);
push_track(temp,entry);
Point cur=entry;
while(1)
{
if(temp->top==-1){
printf("没有找到任何一条出口\n");
return; //栈顶为空 说明回溯结束 没有任何一条出口
}
printf("(%d %d)\n",cur.row,cur.col);//显示出每一步的走的位置
if(Isexit(cur,exit)==1)
{
printf("找到一条出口\n");
return; //当前节点与出口节点相同
}
//若不是出口 则对四周进行探索分四种情况进行讨论
number=back(house,cur);
cur=direc[number];
Mark(house,cur);
push_track(temp,cur);
}
}
以上就是我们需要的所有函数块，其实函数（7）可以直接写进main（）函数，但为了更加清楚，我们将它封装进函数，下面我们贴出代码。
#include<stdio.h>
#include<stdlib.h>
#define ROW 6
#define COL 6
#define maxsize 36
typedef struct
{
int row;//行
int col;//列
}Point;
typedef struct
{
int map[ROW][COL];
}Warehouse;
//定义一个栈 包含入栈和出栈操作
typedef struct
{
int top= -1;
Point shuzu[maxsize]; //这里用一个结构体类型的数组
}track;
//这是一个入栈的操作
int push_track(track *ptrack,Point pPoint)
{
if(ptrack->top==maxsize-1) return 0;
else{
ptrack->shuzu[(ptrack->top)++]=pPoint;
return 1;
}
}
//这是一个出栈的操作
int pop_track(track *ptrack)//第一次写了参数区存储出栈的值 但其实没有什么必要 我们不需要那个值
{
if(ptrack->top==-1) return 0;
else{
ptrack->shuzu[ptrack->top--];
return 0;
}
}
track *create()
{
track *s;
s=(track*)malloc(sizeof(track));
s->top=-1;
return s;
}
//声明一个全局变量的顺序栈
track *temp=create();
void Mark(Warehouse *house,Point cur)
{
if(house==NULL) return;
house->map[cur.row][cur.col]=2;
return;
}
//判断当前点是否为出口
int Isexit(Point cur,Point exit)
{
if(cur.row==exit.row&&cur.col==exit.col)
return 1;
return 0; //是出口返回 1 不是则返回 0
}
Point direc[4];
int back(Warehouse *house,Point cur)
{
direc[0]=direc[1]=direc[2]=direc[3]=cur;
direc[0].col++; //temp[0]测试右边
direc[1].row++; //temp[1]测试上面
direc[2].col--; //temp[2]测试左边
direc[3].row--; //temp[3]测试下面
for(int i=0;i<4;i++)
if(house->map[direc[i].row][direc[i].col]==1)
return i;
for(int i=0;i<4;i++)
{
if(house->map[direc[i].row][direc[i].col]==2) //返回我们下一步需要的位置
{
if(house->map[cur.row][cur.col]==2) house->map[cur.row][cur.col]=3;
pop_track(temp); //如果下一步会走到已走到的位置 在返回时出栈
return i;
}
}
}
//找到终点的函数
void pathstack(Warehouse *house,Point entry,Point exit)
{
int number;
if(house==NULL) return;
Mark(house,entry);
push_track(temp,entry);
Point cur=entry;
while(1)
{
if(temp->top==-1){
printf("没有找到任何一条出口\n");
return; //栈顶为空 说明回溯结束 没有任何一条出口
}
printf("(%d %d)\n",cur.row,cur.col);
if(Isexit(cur,exit)==1){
printf("找到一条出口\n");
return; //当前节点与出口节点相同
}
//若不是出口 则对四周进行探索分四种情况进行讨论
number=back(house,cur);
cur=direc[number];
Mark(house,cur);
push_track(temp,cur);
}
}
main()
{
Warehouse *house;
house=(Warehouse*)malloc(sizeof(Warehouse));
Point entry,exit;
//对入口和出口的初始化
entry.row=0;
entry.col=1;
exit.row=5;
exit.col=2;
int tmp[ROW][COL]=
{
{0,1,0,0,0,0},
{0,1,0,1,1,0},
{0,1,1,0,1,0},
{0,0,1,1,1,0},
{0,0,1,0,0,0},
{0,0,1,0,0,0}
};
int row=0;
int col=0;
for(row;row<ROW;row++)
{
for(col=0;col<COL;col++)
house->map[row][col]=tmp[row][col];
}
for(row=0;row<6;row++)
{
for(col=0;col<6;col++)
printf("%d ",house->map[row][col]);
printf("\n");
}
pathstack(house,entry,exit);
for(row=0;row<6;row++)
{
for(col=0;col<6;col++)
printf("%d ",house->map[row][col]);
printf("\n");
}
}这是一个关于栈的课后习题 以上是我对于这个问题的理解 能帮到解决您现在的问题的话我很荣幸 希望大家能给出自己宝贵的意见 感谢！
最后别忘了点赞哟 > - <！