c++通过用栈来实现迷宫代码

顺序储存
要求搜寻策略是从起点开始按照“上、下、左、右”四个方向寻找终点，到下一个点继续按照“上、下、左、右"四个方面寻找，当该结点四个方向都搜寻完，但还没到终点时，退回到上一个点，直到找到终点或者没有路径。

可以参考下面这个链接。
https://www.jb51.net/article/139370.htm

其中在这部分的代码更换一下位置，改成你的 上，下，左，右的顺序就可以了

如有帮助，请采纳

看看https://blog.csdn.net/qq_51604330/article/details/120783602

如果有用的话麻烦采纳一下奥ღ( ´･ᴗ･` )

#include<iostream>
#include<assert.h>
#include"maze.h"
using namespace std;

#define ROW  6//行
#define COL  6//列

//地图
typedef struct _Maze
{
    int map[ROW][COL];
}Maze;

//根据给出给出的地图数据初始化结构体地图
void initMaze(Maze& m, int map[ROW][COL])
{
    for (int i = 0; i < ROW; i++)
    {
        for (int j = 0; j < COL; j++)
        {
            m.map[i][j] = map[i][j];
        }
    }
}

//打印迷宫(地图)
void printMaze(Maze& m)
{
    for (int i = 0; i < ROW; i++)
    {
        for (int j = 0; j < COL; j++)
        {
            cout << m.map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

//判断是否是有效的入口
bool isValidEnter(Maze* m,Postion enter)
{
    assert(m);//断言-里面的表达式为0直接终止程序,注意里面的内容是什么
    //只要入口在四个边界上就是合法的,并且是1(道路)
    if (((enter._x == 0 || enter._x == ROW - 1) || (enter._y == 0 || enter._y == COL - 1)))
    {
        return true;
    }
    return false;
}

//判断当前位置是否是出口
bool isVaildExit(Maze* m, Postion cur, Postion enter)
{
    assert(m);
    //该结点不能是入口点，除了入口点，在边界上就是合法出口

    if ((cur._x != enter._x || cur._y != enter._y) && ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1)))
    {
        return true;
    }
    else
    {
        return false;
    }
}

//判断当前结点的下一个结点是否能走通-是不是可以走的点
bool isNextPass(Maze* m, Postion cur, Postion next)
{
    assert(m);
    //判断next是不是cur的下一个结点
    //同一行相邻或者同一列相邻
    if (((next._x == cur._x) && ((next._y == cur._y + 1) || (next._y == cur._y - 1)))
        || ((next._y == cur._y) && ((next._x = cur._x + 1) || (next._x = cur._x - 1))))
    {
        //确实是cur的下一个结点(相邻的 )
        //判断这个点是不是在迷宫里
        //合法坐标并且那个位置的值是1
        if (((next._x >= 0 && next._x < ROW) && (next._y >= 0 && next._y < COL)) 
            && (m->map[next._x][next._y] == 1))
            //最后的参数==1，不仅仅是看是否是可以走的位置(道路是1)，
            //同时有了这个我们就不用倒着往往前走了(不走重复的路)，不是有效的结点不只是墙(0)
            //走过的也不是有效结点，直接pop出栈，通过出栈来往前回退
        {
            return true;
        }
    }
    return false;
}

//寻找迷宫通路
bool PassMaze(Maze* m, Postion enter, Stack& s)
{
    assert(m && isValidEnter(m, enter));

    Postion cur = enter;//cur存储当前结点
    Postion next;//下一个结点，从入口开始出发向四周移动

    //先将入口压入栈中
    pushStack(s, cur);
    m->map[cur._x][cur._y] = 2;//将入口值改为2

    //循环求解-当栈中还有路径时
    while (!isEmpty(s))
    {
        cur = *getTop(s);//取到栈顶元素
        //判断当前位置是否是出口
        if (isVaildExit(m, cur, enter))//注意参数传递顺序
        {
            return true;//是出口直接返回
        }
        
        //不是出口继续在周围判断
        //把cur当前刚才那个位置拿过来向四周判断
        
        //先向左判断
        next = cur;
        next._y = cur._y - 1;
        if (isNextPass(m,cur,next))//如果下一个结点走得通
        {
            //走得通就走到那个位置-压进栈
            pushStack(s, next);
            //走过的位置-标记
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;

            //之后
            continue;
        }
        //走不通向另一个方向判断
        //向右走一步
        next = cur;
        next._y = cur._y + 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //向下走一步
        next = cur;
        next._x = cur._x + 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //向上走一步
        next = cur;
        next._x = cur._x - 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //走到这里说明此结点的四个方向都走不通
        //进行回溯
        Postion tmp;//没用 临时接收
        popStack(s, tmp);//出栈

    }
    return false;
}

int main(void)
{
    //0-墙 1-路
    int map[ROW][COL] = {
        0,0,1,0,0,0,
        0,0,1,1,1,0,
        0,0,1,0,0,0, 
        0,1,1,1,1,0,
        0,0,1,0,1,0,
        0,0,0,0,1,0 
    };


    Maze m;//创建一个迷宫(地图)
    initMaze(m, map);//初始化迷宫
    printMaze(m);//打印迷宫

    cout << "_______" << endl;

    //迷宫入口
    Postion enter;
    enter._x = 0;
    enter._y = 2;

    //定义栈
    Stack s;//用于保存走过的轨迹，便于回溯
    initStack(s);//初始化栈

    int ret = PassMaze(&m, enter, s);
    if (ret)
    {
        cout << "有解" << endl;
    }
    else
    {
        cout << "无解" << endl;
    }
    printMaze(m);


    return 0;
}