栈的应用3——迷宫求解问题

为什么用栈

看标题就是老计算机问题了，因为计算机的性质，穷举法是一个很好的方式，那么就需要记录当前点到出口的路径，这时，栈就派上用场了。

规定

1.创建一个二维数组maze，0表示可以通过，1表示不行；
2.因为有八个方向可以走（别问为什么是八个，开始听我也感觉很扯，后来就习惯了），
因为每一个方向都有一个坐标的变化，用二维数组存储避免了每一次都要进行计算。
move数组：（到时候只需要i+move[方向][0]就行了）

3.防止每一次都测试边界，在当前的二维数组加一圈1；
4.另辟一个数组mark，专门存放哪些点是走过的，0&1即可。只有maze为0和mark显示没走过的才能走。
5.栈为三元组，分别为横纵坐标和当前是第几个方向

算法思想：

从（1，1）点出发，按move数组的顺序走每一个能走的方向，
走一个点就压入栈并在marks数组标记，回退就退栈，当前点方向标识v加一，
循环退出的条件的走到了终点坐标或者起始点坐标。
如果最终回退到了（1，1）且这个点的方向数是8，说明这个迷宫没有出去的路。

贴代码：

void work(int maze[m][n],int mark[m-1][n-1])//m,n已经包括了外面的一圈
{
    struct link* head=(struct link* )malloc(sizeof(struct link));
    head->next=NULL;
    int i=1,j=1,v=1;
    int Move[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};//东	南	西	北	东南	东北	西南	西北
    input(head,i,j,v);
    mark[i][j]=1;

    do
    {
        int g=i+Move[v-1][0];
        int h=j+Move[v-1][1];

        if((g==m-2&&h==n-2)&&maze[g][h]&&mark[g][h])//找到了
        {
            cout<<g<< "&"<<h<<endl;
            input(head,i,j,v);
            while(head->next->next)
            {
                output(head,1);
            }
            free(head->next);//这个是起始点，存了两遍但只需要输出一个
            free(head);
            return ;
        }

        if(!maze[g][h] && !mark[g][h])
        {
            input(head,i,j,v);
            mark[g][h]=1;
            i=g;
            j=h;
            v=1;
        }
        else if(v<8)
            v++;
        else
        {
            while(head->next && head->next->v==8)
                output(head,0);
            if(head->next)
            {
                i=head->next->i;
                j=head->next->j;
                v=head->next->v;
                v++;
                output(head,0);
            }
        }
    }while(head->next&&v!=8);
    cout << "No way!"<<endl;
}

这里说明一下

void input(struct link* head,int i,int j,int v);
void output(struct link* head,int input)//输入1就出栈&输出

这两个是压栈和出栈函数。
压栈的就是将三元组压入，出栈和之前有点不同，有一个整型变量控制着是直接弹出还是需要输出。
这点改动还是可以接受的，如果不知道结构建议看一下我之前的栈的应用案例，里面涉及到了栈ADT。

主函数

int main()
{
    int maze[m][n];
    int mark[m-1][n-1]={0};
    for(int i=1;i<m-1;i++)//1不能通过，0可以
    {
        for(int j=1;j<n-1;j++)
        {
            cin>>maze[i][j];
            maze[0][j]=1;
            maze[m-1][j]=1;
        }
        maze[i][0]=1;
        maze[i][n-1]=1;
    }
    maze[0][0]=maze[0][n-1]=maze[m-1][0]=maze[m-1][n-1]=1;

    work(maze,mark);
    return 0;
}

就是将迷宫的边围一下，然后调用work函数，也是很简单的。

本文地址：https://blog.csdn.net/rebortt/article/details/107408584