栈的应用——深度优先搜索（走迷宫）

栈应用到走迷宫（寻路算法）的做法

迷宫就是下图所示的这种，这次主要是先用代码画出一个迷宫（利用二维数组），然后寻路走到出口

代码如下：(在C++中运行)

mystack.h

#include<stdlib.h>
#include<stdio.h>
struct Point  //这个就是显示的坐标点位置，其余都一样，只是data的类型变了，变为坐标
{
        int _x;
        int _y;
};

struct Node
{
        Point data;
        Node* next;
};

struct Stack
{
        Node*top;
};

void initStack(Stack*s);
bool isStackEmpty(Stack*s);
void push(Stack*s,Point data);
Point pop(Stack*s);
void resetStack(Stack*s);
void destroyStack(Stack*s);

mystack.cpp

#include"mystack.h"
void initStack(Stack*s) //这些跟栈的基本一样，除了Point类型
{
    s->top=(Node*)malloc(sizeof(Node));
    s->top->next=NULL;
}
bool isStackEmpty(Stack*s)
{
    return s->top->next==NULL;
}
void push(Stack*s,Point data)
{
    Node *cur=(Node*)malloc(sizeof(Node));
    cur->data=data;
    cur->next=s->top->next;
    s->top->next=cur;
}
Point pop(Stack*s)
{
    Node *t=s->top->next;
    s->top->next=t->next;
    Point ch=t->data;
    free(t);
    return ch;
}
void resetStack(Stack*s)
{
    while(!isStackEmpty(s))
        pop(s);
}
void destroyStack(Stack*s)
{
    resetStack(s);
    free(s->top);
}

main函数(关键！)

#include <iostream>
#include"mystack.h"
#include <windows.h>
#define MAXROW 10
#define MAXLINE 10
//宏定义把迷宫 长宽都定义成10
using namespace std;
Stack s;  //变成全局，方便调用
int maze[MAXROW][MAXLINE] =     //这里就是画一个10*10的迷宫，0代表能走的路
{
    1,1,1,1,1,1,1,1,1,1,
    0,0,0,1,1,1,1,1,1,1,
    1,1,0,1,1,1,1,1,1,1,
    1,1,0,0,0,0,1,1,1,1,
    1,1,0,1,1,0,1,1,1,1,
    1,1,0,1,0,0,0,1,1,1,
    1,1,1,1,1,0,1,1,1,1,
    1,1,1,1,1,0,0,0,1,1,
    1,1,1,1,1,1,1,0,0,0,
    1,1,1,1,1,1,1,1,1,1,
};

void displyMaze()
{
    for(int i=0; i< MAXROW; i++)
    {
        for(int j=0; j<MAXLINE; j++)
        {
            if(maze[i][j] == 1) printf("%2s"," *");          //代表迷宫的墙
            else if(maze[i][j] == 2) printf("%2s"," #"); //代表走过的路，用#代表
            else printf("%2s"," ");                               //代表迷宫的路
        }
        putchar(10);
    }
    printf(" ====================\n");
}

void visit(int x,int y)
{
    Point p={x,y};
    push(&s,p);
}

int main()
{
   // displyMaze();
    Point sp={1,0},ep={8,9};//迷宫起点和终点（结构体只能这样初始化）

    // 这里要寻路，用了栈的思想，把下一步压入栈，走到这步，弹出，
    // 这样就能走完一步标记一步，而且若遇到分岔口，几条路的下一步都压入栈
//寻路的基本原理,就是压栈出栈,若能压栈,就出栈,再寻找上下左右能继续压栈出栈的位
    initStack(&s);
    push(&s,sp);
    int flag=1;

    while(!isStackEmpty(&s))
    {
        Point t;
        t=pop(&s);              //弹出栈里存的点（这个点就是当前位置的点）
        maze[t._x][t._y]=2;  //表示走过的路，标记为 2

        system("cls");    //这是自动寻路刷新界面，然后有寻路动画
        displyMaze();
        Sleep(100);

        //竖是x轴. 横是y轴（数组的原理）
        //判断各方向的点能不能走，1.坐标从0开始 2.不能是死路 3.不能是走过的路   

        //上
        if(t._x-1>=0&&maze[t._x-1][t._y] == 0)
            visit(t._x-1,t._y);
        //下
        if(t._x+1<=9&&maze[t._x+1][t._y] == 0)
            visit(t._x+1,t._y);
        //左
        if(t._y-1>=0&&maze[t._x][t._y-1] == 0)
            visit(t._x,t._y-1);
        //右
        if(t._y+1<=9&&maze[t._x][t._y+1] == 0)
            visit(t._x,t._y+1);

        if(t._x==ep._x&&t._y==ep._y)
        {
            flag=0;    //给定找到出口的标志位
            destroyStack(&s);
            break;
        }

    }
    if(flag==0)
    {
          cout<<"find path"<<endl;
    }
    else
        cout<<"find no path"<<endl;
    return 0;
}

寻路遇到岔路口的话，这时候主要是看上下左右的顺序，后压入栈的，会继续在后压入栈的这条路上继续走下去，如果走到死胡同，便继续回到原来岔路口，压入栈的地方。
我这里代码，具体压入栈的顺序是上下左右，那么最先判断的是右边，最后才是上。然后若走进死路，那最先判断的是上一个压入栈的地方，那就是离他最近的岔路口。

这是利用的栈思想寻路的关键，这是深度优先搜索，一条路走到底再换一条路。可以自行改变上下左右顺序或者改变迷宫都可以看出。