【C++数据结构】基于栈与深度优先搜索算法实现的迷宫问题

桃扇骨 2024-03-31 15:54 41阅读 0赞

声明：未经允许，请勿转载

标题：基于栈与深度优先搜索算法的迷宫问题求解

摘要：本文介绍了使用栈和深度优先搜索算法解决迷宫问题的代码实现。通过定义二维数组表示迷宫地图，利用栈记录路径信息，并使用深度优先搜索算法进行路径搜索，最终找到从起点到终点的通路。文章详细介绍了实验目的、实验步骤以及代码实现过程，并展示了实验结果和结论。同时，还提出了进一步扩展功能和优化算法的展望。

一、引言  
迷宫问题是计算机科学中常见的问题之一，解决迷宫问题需要通过搜索算法来找到从起点到终点的路径。本文将介绍一种基于栈和深度优先搜索算法的迷宫问题求解方法，该方法能够找到一条从左上角到右下角的通路。

二、实验目的及要求  
本实验的目的是通过栈和深度优先搜索算法解决迷宫问题，具体要求如下：  
1. 定义一个二维数组表示迷宫地图，其中元素的值为1表示墙壁，值为0表示可以走通。  
2. 确保迷宫有解，即存在一条从左上角到右下角的通路。  
3. 只能横向或纵向移动，不能斜向移动。

三、实验步骤  
1. 创建一个二维数组，表示迷宫地图。将墙壁标记为1，可通行的路径标记为0。  
2. 定义一个迷宫方块的结构体，包含方块的位置坐标和值。  
3. 实现栈的基本操作，包括初始化栈、判断栈是否为空、入栈和出栈操作。  
4. 定义一个深度优先搜索函数DFS，函数参数包括当前点的坐标、上一个点的坐标以及上一个点的地图值。在DFS函数内部，通过递归调用实现对不同方向的深度搜索。如果当前位置可行，则将该位置的信息入栈。如果该位置已经访问过或者是墙壁，则返回。如果四个方向都走完且不能继续前进，则回退到上一个点，并将该点的信息出栈，恢复进入函数时的参数状态。  
5. 根据栈中元素对应的点的值进行修改，然后通过打印函数PrintMap绘制迷宫和人物行走路径的图形。

四、实验结果  
经过深度优先搜索算法的遍历，成功找到了从左上角到右下角的通路。在程序运行过程中，栈记录了访

问路径，并根据栈中保存的信息修改了地图的访问路径。最终，打印出了访问过的路径图，展示了主角的行走路径。

五、结论  
本实验通过栈和深度优先搜索算法实现了迷宫问题的求解。深度优先搜索算法通过递归地探索各个可能的路径，并回溯到上一个节点，能够找到从起点到终点的通路。栈的使用能够记录访问路径，方便回溯操作。通过这种算法的应用，我们能够解决类似的迷宫问题，找到通路并进行路径的可视化展示。

由于使用深度优先算法 DFS，则会优先往一个方向走直到这个位置访问过或者是墙壁等，则 往其他方向走。若四个方向都走完，不能走，则说明这个位置不能通过，需要回退到上一个点，同 时将该点的信息出栈，并恢复进入函数时改变的参数。 ○4 通过不断递归调用 DFS 函数，直至得到出口，则退出递归。 走迷宫遵循的 下-右-左-上 的原则

![ce3a8ed9d3e949d5ad5ba57bc86fc6b5.png][]

结果展示：

![a243d53df5154b5094029e0420f78ca7.png][]

【C++数据结构】 基于栈与深度优先搜索算法实现的迷宫问题

#include <iostream>
    #include <stack>
    #include <windows.h>
    using namespace std;
    
    // 地图值: 1是墙壁，0是通道，2是主角所在位置，3是出口 4是不能通过的标记
    #define WALL 1
    #define PASS 0
    #define ZHUJUE 2
    #define EXITS 3
    #define NOPATH 4
    
    // 全局变量
    int m = 10, n = 10; // 行和列 默认为10
    int vis[100][100];  // 是否访问过，0是没访问，-1是访问过了
    bool isFind = false;  // 是否找到出口
    stack<int (*)> s;  // 用STL模板的栈类记录路径
    int map[10][10] = {
       {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                       {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
                       {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
                       {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
                       {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
                       {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
                       {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
                       {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
                       {1, 0, 0, 0, 0, 1, 0, 0, 0, 1},
                       {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
    
    // 打印地图值
    void PrintMap(int flag)
    {
        if (flag == 0)
        {
            COORD position;
            position.X = 0;
            position.Y = 0;
            SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), position);
            cout << "搜索地图中..............." << endl;
        }
        Sleep(250); // 休眠0.25秒，更新输出内容
    
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i][j] == ZHUJUE)
                { // 主角当前所在位置
                    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 12); // 红色
                    cout << "☆";
                    continue;
                }
                SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0x07); // 白色字体
                if (map[i][j] == WALL || map[i][j] == EXITS)
                { // 墙
                    cout << "■";
                }
                if (map[i][j] == PASS)
                { // 路
                    cout << "  "; // 要2个空格
                }
                if (map[i][j] == NOPATH)
                { // 不能通过
                    cout << "×";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    
    /*
    思路：采用深度优先搜索
    递归中自带“栈特性”，在进入当前递归函数相当于栈的push，退出当前递归函数相当于栈的pop
    那么根据这个特性，实现搜索地图中返回上一个结点的功能。
    */
    void DFS(int cury, int curx, int lasty, int lastx, int ysval)
    {
        if (isFind)
        { // 找到了出口，递归栈都返回
            return;
        }
        if (vis[cury][curx] == -1 || map[cury][curx] == 1 || cury >= m || cury < 0 || curx >= n || curx < 0)
        { // 递归返回条件:这个位置访问过，墙壁，越界，
            return;
        }
        if (map[cury][curx] == EXITS)
        { // 递归退出条件，找到了出口
            // cout << "找到了出口" << endl;
            isFind = true;
            return;
        }
    
        // 递归函数执行时，执行相当于栈push时的操作
        s.push(new int[2]{cury, curx});   // 记录当前路径
        vis[cury][curx] = -1;              // 表示访问过当前点
        int curysval = map[cury][curx];    // 保存当前的地图值
        // 更新主角所在位置。
        map[lasty][lastx] = ysval;         // 上一个所在的位置变回地图值
        map[cury][curx] = ZHUJUE;          // 现在所在的位置为2，
        PrintMap(0);                       // 递归函数执行时，当前的地图值
    
        // 上下左右四个方向探索，并传入当前位置和当前的地图值（以便在下一个递归函数把当前主角所占的位置变回地图值）
        DFS(cury, curx + 1, cury, curx, curysval); // 先向右边探索，为了符合PPT上的图展示效果，不过应该优先向下探索的。
        DFS(cury + 1, curx, cury, curx, curysval); // 向下边探索
        DFS(cury, curx - 1, cury, curx, curysval); // 向左边探索
        DFS(cury - 1, curx, cury, curx, curysval); // 向上边探索
    
        if (isFind)
        { // 找到了出口，现在的路径栈保存了正确的访问路径，退出即可，但是这个路径可能不是最优路径
            return;
        }
    
        // 4个方向都走完了，无路可走，说明这个位置不能通过，需要返回上一个位置
        // 递归函数结束时，相当于栈pop时的操作
        // 需要把递归函数进入时改变的数值等操作回归原位
        //vis[cury][curx] = 0;                      // 当前点没访问过，去掉没影响，但恢复为0可能可以找到最优路径
        s.pop();                          // 舍去记录当前位置
        map[cury][curx] = NOPATH;         // 这个位置的值为不能通过
        map[lasty][lastx] = ZHUJUE;       // 上一个所在的位置为2
        PrintMap(0);                       // 打印当前的地图值
    }
    
    // 根据栈保存的路径值，修改地图值
    void UpdateMapToPath()
    {
        while (!s.empty())
        {
            int *pos = s.top();
            s.pop();
            map[*pos][*(pos + 1)] = 2;
        }
    }
    
    int main()
    {
    
        int endy = m - 2, endx = n - 1; // 出口列和行，列是x，y是行
        int curx = 1, cury = 1;         // 主角所在的开始行和列
        map[endy][endx] = EXITS;        // 给出口位置标记
        system("cls");                  // 清空输入
    
        // 2.深度优先搜索，找到路径
        DFS(cury, curx, cury, curx, map[cury][curx]);
    
        // 3.根据栈保存的信息，修改地图访问的路径
        cout << "成功找到出口，访问出口路径如下:" << endl;
        UpdateMapToPath();
        PrintMap(1); // 最后打印访问过的路径图
        system("pause");
    }

[ce3a8ed9d3e949d5ad5ba57bc86fc6b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9c720a30829e4ee1b46289f87872428a.png
[a243d53df5154b5094029e0420f78ca7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6fc3a2eeda314be5a7b744b341066e6a.png