数据结构迷宫旅行问题

Question

数据结构实验：
1.迷宫旅行问题：
设计一个迷宫，动态的展示迷宫路径探索的过程。展示从路口到出口的所有通路，指出从入口到出口路径最短的一条，又或者得出没有通路的结论。
（1） 能动态展示迷宫路径探索的过程
（2） 展示能够从入口到达出口的所有通路
（3） 指出从入口到出口路径最短的一条
（4） 迷宫能够动态生成
不会啊，好难。动态演示，不用太高端，就是能走出路线那种，

最好使用c++/c语言编写，不用太高级界面，就能粗略地演示出走法就行

Answer 1

引自免费微信小程序：皆我百晓生

解决这个问题的关键是使用广度优先搜索（BFS）算法，它可以从起点开始逐层遍历迷宫，直到找到终点。这里是一个简单的C++实现，包括动态生成迷宫、显示路径以及找出最短路径的功能。为了简化问题，我们将使用二维数组表示迷宫，其中0表示可以通行，1表示障碍物，-1表示已经访问过。

首先，我们需要定义一个结构体来表示节点：

struct Node {
    int x, y; // 节点坐标
    int parentX, parentY; // 上一节点坐标
};

接下来，我们创建一个函数来生成随机迷宫：

#include <ctime>
#include <cstdlib>

void generateMaze(int maze[10][10]) {
    std::srand(std::time(0)); // 设置随机数种子
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            maze[i][j] = (std::rand() % 3 == 0) ? 1 : 0;
        }
    }

    // 添加起点和终点
    maze[0][0] = -1; // 假设起点在左上角 (0, 0)
    maze[9][9] = -1; // 假设终点在右下角 (9, 9)
}

然后，实现广度优先搜索算法：

#include <queue>
#include <vector>

std::vector<std::pair<int, int>> bfs(const int maze[10][10], int startX, int startY) {
    std::queue<Node> q;
    q.push({startX, startY});

    std::vector<std::pair<int, int>> path;

    while (!q.empty()) {
        Node node = q.front();
        q.pop();

        if (node.x == 9 && node.y == 9) { // 找到了终点
            path.push_back({node.x, node.y});
            while (node.parentX != -1 || node.parentY != -1) {
                path.push_back({node.parentX, node.parentY});
                node = {node.parentX, node.parentY};
            }
            std::reverse(path.begin(), path.end()); // 反转路径
            return path;
        }

        // 遍历邻居节点
        if (node.x > 0 && maze[node.x - 1][node.y] == 0) {
            maze[node.x - 1][node.y] = -1;
            q.push({node.x - 1, node.y});
        }
        if (node.x < 9 && maze[node.x + 1][node.y] == 0) {
            maze[node.x + 1][node.y] = -1;
            q.push({node.x + 1, node.y});
        }
        if (node.y > 0 && maze[node.x][node.y - 1] == 0) {
            maze[node.x][node.y - 1] = -1;
            q.push({node.x, node.y - 1});
        }
        if (node.y < 9 && maze[node.x][node.y + 1] == 0) {
            maze[node.x][node.y + 1] = -1;
            q.push({node.x, node.y + 1});
        }
    }

    return {}; // 没有找到路径
}

最后，我们可以创建一个主函数来运行这个程序：

int main() {
    int maze[10][10];
    generateMaze(maze);

    std::vector<std::pair<int, int>> shortestPath = bfs(maze, 0, 0);
    if (shortestPath.empty()) {
        std::cout << "No path found.\n";
    } else {
        std::cout << "Shortest path: ";
        for (const auto& step : shortestPath) {
            std::cout << "(" << step.first << ", " << step.second << ") ";
        }
        std::cout << "\n";
    }

    return 0;
}

这段代码会生成一个10x10的随机迷宫，并尝试从左上角走到右下角。如果找到了路径，它将打印出最短路径；如果没有找到路径，则输出"No path found."。

注意：由于这是一个控制台应用程序，动态展示路径探索过程可能需要额外的图形库来实现，例如ncurses或者Windows API。如果你想要在窗口中可视化迷宫，你需要使用更复杂的图形库，如OpenGL、DirectX或者一些基于HTML5的前端框架。这超出了本问题的范围，但你可以考虑使用这些技术来进一步改进你的项目。