迷宫数据结构问题c++

迷宫问题是一种常见的图论问题，在C++中通常会用到广度优先搜索（BFS）或深度优先搜索（DFS）算法来解决。数据结构方面，一种常见的是邻接矩阵（二维数组），它表示每个网格单元与其相邻单元之间的连接；另一种是邻接表，通过链表存储每个节点的邻居。

C++代码示例（使用BFS）：

#include <iostream>
#include <vector>
#include <queue>

// 定义迷宫状态
enum class CellState { Empty, Wall };

class Maze {
private:
    std::vector<std::vector<CellState>> maze; // 使用二维向量表示迷宫

public:
    // 初始化迷宫，空格表示可以通行，墙表示障碍
    void initializeMaze(int rows, int cols) {
        maze.resize(rows);
        for (int i = 0; i < rows; ++i)
            maze[i].resize(cols, CellState::Empty);
    }

    // 检查某个位置是否可达
    bool isAccessible(int x, int y) {
        return x >= 0 && y >= 0 && x < maze.size() && y < maze[0].size() && maze[x][y] == CellState::Empty;
    }

    // BFS解迷宫
    std::pair<int, int> solveMaze(int startX, int startY) {
        std::vector<bool> visited(maze.size() * maze[0].size(), false);
        std::queue<std::pair<int, int>> q {{startX, startY}};
        visited[startX * maze[0].size() + startY] = true;

        while (!q.empty()) {
            auto [currentX, currentY] = q.front();
            q.pop();

            // 检查四个方向
            if (isAccessible(currentX - 1, currentY) && !visited[currentX - 1 * maze[0].size() + currentY])
                q.push({currentX - 1, currentY}), visited[currentX - 1 * maze[0].size() + currentY] = true;
            if (isAccessible(currentX + 1, currentY) && !visited[currentX + 1 * maze[0].size() + currentY])
                q.push({currentX + 1, currentY}), visited[currentX + 1 * maze[0].size() + currentY] = true;
            if (isAccessible(currentX, currentY - 1) && !visited[currentX * maze[0].size() + currentY - 1])
                q.push({currentX, currentY - 1}), visited[currentX * maze[0].size() + currentY - 1] = true;
            if (isAccessible(currentX, currentY + 1) && !visited[currentX * maze[0].size() + currentY + 1])
                q.push({currentX, currentY + 1}), visited[currentX * maze[0].size() + currentY + 1] = true;

            // 如果找到终点，返回路径坐标
            if (currentX == maze.size() - 1 && currentY == maze[0].size() - 1)
                return {currentX, currentY};
        }
        return {-1, -1}; // 未找到路径
    }
};

int main() {
    Maze maze;
    maze.initializeMaze(5, 5); // 示例迷宫大小
    auto result = maze.solveMaze(0, 0); // 从左上角开始
    if (result.first != -1 && result.second != -1)
        std::cout << "Solution found at (" << result.first << ", " << result.second << ")";
    else
        std::cout << "No solution found.";
    return 0;
}