C++ 迷宫

2025年2月10日 | 阅读12分钟

引言

C++ 中的迷宫通常指的是一个用于生成、导航或解决迷宫的程序或算法。迷宫是计算问题解决中引人入胜的结构，通常涉及基于网格的布局，其中包含墙壁、路径以及起点和终点。在 C++ 中实现迷宫利用了诸如数组或向量之类的基本编程概念来表示网格，并使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 算法来导航或解决迷宫。

过程始于定义迷宫的结构。通常，它是一个二维数组，其中每个单元格可以是墙壁或路径。迷宫生成可以采用递归回溯、Prim's 或 Kruskal's 等算法，这些算法可确保生成可解的迷宫，并在起点和终点之间具有连续的路径。一旦生成，解决迷宫就涉及通过此网格找到路径，利用 DFS、BFS 或 A* 算法。

方法 1：C++ 中的迷宫实现

程序

#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <ctime>
const int WIDTH = 10;
const int HEIGHT = 10;
enum Cell {
    WALL,
    PATH,
    START,
    END
};
struct Position {
    int x, y;
};
std::vector<std::vector<Cell>> createMaze(int width, int height) {
    std::vector<std::vector<Cell>> maze(height, std::vector<Cell>(width, WALL));
    std::stack<Position> stack;
    Position current{1, 1};
    stack.push(current);
    maze[current.y][current.x] = PATH;
    while (!stack.empty()) {
        std::vector<Position> neighbors;
        if (current.x > 1 && maze[current.y][current.x - 2] == WALL)
            neighbors.push_back({current.x - 2, current.y});
        if (current.x < width - 2 && maze[current.y][current.x + 2] == WALL)
            neighbors.push_back({current.x + 2, current.y});
        if (current.y > 1 && maze[current.y - 2][current.x] == WALL)
            neighbors.push_back({current.x, current.y - 2});
        if (current.y < height - 2 && maze[current.y + 2][current.x] == WALL)
            neighbors.push_back({current.x, current.y + 2});
        if (!neighbors.empty()) {
            Position next = neighbors[rand() % neighbors.size()];
            stack.push(next);
            maze[(current.y + next.y) / 2][(current.x + next.x) / 2] = PATH;
            maze[next.y][next.x] = PATH;
            current = next;
        } else {
            current = stack.top();
            stack.pop();
        }
    }
    maze[1][1] = START;
    maze[height - 2][width - 2] = END;
    return maze;
}
bool solveMaze(std::vector<std::vector<Cell>>& maze, Position current, std::vector<Position>& path) {
    if (current.x < 0 || current.x >= WIDTH || current.y < 0 || current.y >= HEIGHT)
        return false;
    if (maze[current.y][current.x] == WALL || maze[current.y][current.x] == START)
        return false;
    if (maze[current.y][current.x] == END) {
        path.push_back(current);
        return true;
    }
    maze[current.y][current.x] = START; // Mark as part of the solution path
    static const std::vector<Position> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    for (const auto& dir : directions) {
        Position next{current.x + dir.x, current.y + dir.y};
        if (solveMaze(maze, next, path)) {
            path.push_back(current);
            return true;
        }
    }
    maze[current.y][current.x] = PATH; // Unmark if it is not the solution path
    return false;
}
void printMaze(const std::vector<std::vector<Cell>>& maze) {
    for (const auto& row : maze) {
        for (const auto& cell : row) {
            if (cell == WALL)
                std::cout << "#";
            else if (cell == PATH)
                std::cout << " ";
            else if (cell == START)
                std::cout << "S";
            else if (cell == END)
                std::cout << "E";
        }
        std::cout << std::endl;
    }
}
int main() {
    srand(time(nullptr));
    std::vector<std::vector<Cell>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    std::vector<Position> path;
    if (solveMaze(maze, {1, 1}, path)) {
        std::cout << "\nSolved Maze:" << std::endl;
        for (const auto& pos : path) {
            maze[pos.y][pos.x] = START;
        }
        maze[1][1] = START;
        maze[HEIGHT - 2][WIDTH - 2] = END;
        printMaze(maze);
    } else {
        std::cout << "\nNo solution found." << std::endl;
    }
    return 0;
}

输出

Generated Maze:
##########
#S#       
# ##### # 
#   #   # 
### # ### 
# # #   # 
# # ### # 
# #   # # 
# ### # E 
#       # 
No solution found.

说明

初始化

迷宫表示为单元格的二维网格，其中每个单元格可以是墙壁或路径。迷宫的尺寸由常量 WIDTH 和 HEIGHT 定义。

迷宫初始时所有单元格都设置为墙壁。

算法选择

迷宫使用递归回溯算法生成。该算法使用堆栈来跟踪当前位置及其邻居。

起点

选择起始位置，通常是坐标 (1, 1)，将其标记为路径以开始迷宫创建。

挖洞

该算法会迭代地选择一个当前单元格，然后随机选择一个相距两个单元格的未访问邻居单元格（以确保路径的创建在墙壁之间）。

它会移除当前单元格与选定邻居之间的墙壁，从而有效地挖出一条路径。

选定的邻居成为新的当前单元格，过程重复。如果没有可用的未访问邻居，算法将使用堆栈回溯到前一个单元格，直到找到一个具有未访问邻居的单元格。

迷宫完成

过程持续进行，直到所有单元格都被访问，从而确保整个网格形成一个连通的迷宫。

起点和终点被明确标记，通常是起点 (1, 1)，终点是 (width-2, height-2)。

迷宫求解

初始化

求解器使用递归深度优先搜索 (DFS) 方法从起点找到到达终点的路径。

标记起始位置，算法尝试从当前单元格向所有四个可能方向（上、下、左、右）移动。

路径查找

对于每一步移动，算法会检查它是否在迷宫边界内，以及它是否通往一个未访问的路径或终点单元格。

如果到达终点单元格，则认为已找到路径，并将当前位置添加到解决方案路径中。

回溯

如果某个移动没有导致解决方案，算法会通过再次将单元格标记为路径来回溯，并尝试下一个可能的方向。

这种回溯会一直持续，直到找到一条通往终点的有效路径，或者所有可能性都被穷尽。

标记解决方案

找到解决方案路径后，它会在迷宫上进行标记。解决方案路径中的单元格会被明显标记，通常是通过改变其状态以指示它们是解决方案的一部分。

输出

迷宫显示

迷宫在求解之前和之后都会在控制台打印出来。在初始打印中，墙壁用特定字符（例如 '#'）表示，路径用空格表示，起点用 'S' 表示，终点用 'E' 表示。

已解决的迷宫

求解后，求解器找到的路径会在迷宫上显示出来，展示了一条从起点到终点的清晰路线。

复杂度分析

时间复杂度

迷宫生成

使用递归回溯算法生成迷宫的时间复杂度为 O(W * H)，其中 W 是宽度，H 是迷宫的高度。这是因为迷宫中的每个单元格都被访问一次以挖出路径。

迷宫求解

使用深度优先搜索 (DFS) 算法解决迷宫的时间复杂度为 O(W * H)。这是因为在最坏情况下，为了找到从起点到终点的路径，可能需要探索所有单元格。

空间复杂度

迷宫生成

生成迷宫的空间复杂度为 O(W * H)，用于存储迷宫网格本身。

用于回溯的堆栈在最坏情况下可以容纳 O(W * H) 个单元格，当每个单元格在回溯开始之前都被推送到堆栈中时。

迷宫求解

解决迷宫的空间复杂度为 O(W * H)，用于路径存储。

此外，DFS 的递归调用堆栈在最坏情况下深度可达 O(W + H)，在基于网格的迷宫场景中通常简化为 O(W * H)。

方法 2：使用 Prim's 算法生成迷宫

引言

Prim's 算法是一种经典的算法，最初用于查找加权图中的最小生成树。然而，它可以改编用于生成迷宫，方法是将迷宫视为一个无向图，其中每个单元格是一个节点，每个单元格之间的墙壁是一条边。该算法可确保生成的迷宫是完美的，这意味着没有循环，并且任意两个点之间只有一条唯一的路径。

程序

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <set>
const int WIDTH = 10;
const int HEIGHT = 10;
enum Cell {
    WALL,
    PATH,
    START,
    END
};
struct Position {
    int x, y;
};
std::vector<std::vector<Cell>> createMaze(int width, int height) {
    std::vector<std::vector<Cell>> maze(height, std::vector<Cell>(width, WALL));
    std::set<std::pair<int, int>> frontier;
    auto addFrontier = [&](int x, int y) {
        if (x >= 1 && x < width - 1 && y >= 1 && y < height - 1 && maze[y][x] == WALL) {
            frontier.insert({x, y});
        }
    };
    srand(time(nullptr));
    Position start = {1, 1};
    maze[start.y][start.x] = PATH;
    addFrontier(start.x, start.y);
    while (!frontier.empty()) {
        auto it = frontier.begin();
        std::advance(it, rand() % frontier.size());
        Position current = {it->first, it->second};
        frontier.erase(it);
        std::vector<Position> neighbors;
        if (maze[current.y - 2][current.x] == PATH) neighbors.push_back({current.x, current.y - 2});
        if (maze[current.y + 2][current.x] == PATH) neighbors.push_back({current.x, current.y + 2});
        if (maze[current.y][current.x - 2] == PATH) neighbors.push_back({current.x - 2, current.y});
        if (maze[current.y][current.x + 2] == PATH) neighbors.push_back({current.x + 2, current.y});
        if (!neighbors.empty()) {
            Position neighbor = neighbors[rand() % neighbors.size()];
            maze[(current.y + neighbor.y) / 2][(current.x + neighbor.x) / 2] = PATH;
            maze[current.y][current.x] = PATH;
            addFrontier(current.x + 2, current.y);
            addFrontier(current.x - 2, current.y);
            addFrontier(current.x, current.y + 2);
            addFrontier(current.x, current.y - 2);
        }
    }
    maze[1][1] = START;
    maze[height - 2][width - 2] = END;
    return maze;
}
void printMaze(const std::vector<std::vector<Cell>>& maze) {
    for (const auto& row : maze) {
        for (const auto& cell : row) {
            if (cell == WALL)
                std::cout << "#";
            else if (cell == PATH)
                std::cout << " ";
            else if (cell == START)
                std::cout << "S";
            else if (cell == END)
                std::cout << "E";
        }
        std::cout << std::endl;
    }
}
int main() {
    std::vector<std::vector<Cell>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    return 0;
}

输出

Generated Maze:
##########
#S########
##########
##########
##########
##########
##########
##########
########E#
##########

说明

初始化

从一个所有单元格都是墙壁的网格开始。

选择一个随机起始单元格，将其标记为迷宫的一部分，方法是将其从墙壁转换为路径。

边界列表

维护一个边界单元格的列表（或集合）。这些是与已转换为路径的单元格相邻但本身仍是墙壁的单元格。

选择边界单元格

从边界列表中随机选择一个单元格。

这种随机选择可确保迷宫具有更不可预测和多样的结构。

连接单元格

从选定的边界单元格，找到其属于迷宫的邻居单元格（即，已从墙壁转换为路径的单元格）。

如果选定单元格只有一个属于迷宫的邻居单元格，则移除选定单元格与其邻居之间的墙壁。此操作会将选定单元格转换为路径并将其连接到现有迷宫。

更新边界列表

将选定的边界单元格标记为迷宫的一部分。

将新相邻的墙壁单元格添加到边界列表中，因为这些单元格现在与新转换的路径单元格相邻，并有可能在下一步被转换。

重复过程

重复选择随机边界单元格、将其连接到迷宫并更新边界列表的过程，直到所有单元格都成为迷宫的一部分。

复杂度分析

时间复杂度

Prim's 算法用于迷宫生成的时间复杂度为 O(W * H)，其中 W 是宽度，H 是迷宫的高度。这是因为迷宫中的每个单元格都会被访问和处理一次。

空间复杂度

空间复杂度为 O(W * H)，用于存储迷宫网格。此外，边界列表（或集合）在最坏情况下可以包含 O(W * H) 个单元格，但在实践中通常小得多，因为单元格会逐渐添加和删除。因此，总空间复杂度保持为 O(W * H)。

方法 3：使用 Kruskal's 算法生成迷宫

Kruskal's 算法 用于迷宫生成，它基于为迷宫网格生成最小生成树 (MST) 的概念。在此方法中，迷宫开始时每个单元格都是孤立的，单元格之间的墙壁构成图的边。然后，Kruskal's 算法会迭代地随机选择边（墙），如果它们不形成循环，则将它们添加到迷宫中，并继续进行，直到所有单元格都连接起来。结果是一个没有循环或孤立部分的迷宫，确保迷宫中的任意两点之间只有一条路径。

程序

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
const int WIDTH = 10;
const int HEIGHT = 10;
struct Edge {
    int cell1, cell2;
};
std::vector<int> parent;
int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    parent[rootX] = rootY;
}
std::vector<Edge> generateEdges(int width, int height) {
    std::vector<Edge> edges;
    for (int y = 1; y < height - 1; ++y) {
        for (int x = 1; x < width - 1; ++x) {
            edges.push_back({y * width + x, y * width + x + 1});
            edges.push_back({y * width + x, (y + 1) * width + x});
        }
    }
    std::random_shuffle(edges.begin(), edges.end());
    return edges;
}
std::vector<std::vector<char>> createMaze(int width, int height) {
    std::vector<std::vector<char>> maze(height, std::vector<char>(width, '#'));
    parent.resize(width * height);
    for (int i = 0; i < width * height; ++i) parent[i] = i;
    std::vector<Edge> edges = generateEdges(width, height);
    for (const auto& edge : edges) {
        int cell1 = edge.cell1;
        int cell2 = edge.cell2;
        if (find(cell1) != find(cell2)) {
            unite(cell1, cell2);
            if (cell2 - cell1 == 1) maze[cell1 / width][cell1 % width] = ' ';
            else maze[cell2 / width][cell2 % width] = ' ';
        }
    }
    return maze;
}
void printMaze(const std::vector<std::vector<char>>& maze) {
    for (const auto& row : maze) {
        for (char cell : row) std::cout << cell;
        std::cout << std::endl;
    }
}
int main() {
    srand(time(nullptr));
    std::vector<std::vector<char>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    return 0;
}

输出

Generated Maze:
##########
# #      #
# #    # #
## #  ## #
#        #
#        #
# ##     #
#        #
#   # #  #
#        #

说明

不相交集数据结构

该算法使用不相交集数据结构来管理已连接单元集的集合。每个集合代表迷宫的一个不相交的组件。

查找和合并操作

find 函数通过递归遍历父指针来查找集合的根（代表）。

unite 函数通过将一个集合的根设置为另一个集合的根的父节点来合并两个集合。

生成边

generate edges 函数创建迷宫网格中相邻单元格之间的边（墙）列表。

边表示为单元格索引对。

迷宫创建

createMaze 函数使用墙壁 ('#') 初始化迷宫网格，并为每个单元格创建不相交集。

它遍历打乱的边列表，尝试合并由每条边连接的单元格的集合。

如果集合不相交，表明添加边不会形成循环，则通过移除单元格之间的墙壁将该边添加到迷宫中。

迷宫是逐步构建的，确保连通性而不形成循环。

打印迷宫

printMaze 函数将生成的迷宫网格打印到控制台，用 '#' 表示墙壁，用空格表示路径。

复杂度分析

时间复杂度

Kruskal's 算法用于迷宫生成的时间复杂度取决于边的排序和并查集操作。

边排序：对边进行排序通常需要 O(E log E) 时间，其中 E 是迷宫网格中的边数。

并查集操作：对每条边执行并查集操作大约需要 O(E α(V)) 时间，其中 V 是单元格（顶点）的数量，α 是反阿克曼函数，它增长得非常慢，对于实际目的几乎是常数。

边的排序决定了整体时间复杂度，通常为 O(E log E)。

空间复杂度

Kruskal's 算法的空间复杂度主要用于存储迷宫网格和不相交集数据结构。

迷宫网格：迷宫网格本身需要 O(W * H) 空间，其中 W 是宽度，H 是迷宫的高度。

不相交集数据结构：不相交集数据结构需要 O(W * H) 空间来存储父指针和集合大小。

因此，总体空间复杂度为 O(W * H)。

性质

连接性

连通的迷宫确保入口到出口至少存在一条路径，并且每个单元格都可以从任何其他单元格到达。此属性对于确保迷宫的可解性和防止可能阻碍导航的孤立部分至关重要。

唯一性

迷宫生成的唯一性意味着生成的每个迷宫都与其他迷宫不同，为用户提供了新颖的挑战或体验。虽然完全的唯一性可能并不总是可实现或必需的，但最小化重复可以增强生成迷宫的吸引力和多样性。

复杂度

迷宫的复杂性包括墙壁密度、死胡同、分支路径和整体大小等因素。更复杂的迷宫通常对解决者来说挑战更大，需要更深入的探索和策略。

可解性

可解性确保迷宫的起点到终点至少存在一条有效路径。虽然某些应用程序可能允许不可解迷宫作为挑战的一部分，但确保可解性对于迷宫求解算法产生有意义的结果至关重要。

下一个主题C++ 中的二叉树逆时针螺旋遍历

C++ 迷宫

引言

方法 1：C++ 中的迷宫实现

程序

方法 2：使用 Prim's 算法生成迷宫

程序

方法 3：使用 Kruskal's 算法生成迷宫

程序

性质

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 迷宫

引言

方法 1：C++ 中的迷宫实现

程序

方法 2：使用 Prim's 算法生成迷宫

程序

方法 3：使用 Kruskal's 算法生成迷宫

程序

性质

相关帖子

C++ 虚函数与纯虚函数的区别

C++ 集合覆盖问题

C++ 中在无限二元流中查找模式 I

C++ 中的 D'Esopo-Pape 算法：单源最短路径

C++ 中的拉姆波特面包店算法

C++ 中的恩特林格数

C++ 21 点游戏

C++ 中的最长交替子序列

C++ 中 Debug 和 Release 构建的区别

C++ 中的 std::get_money

订阅 Tpoint Tech

联系信息