迷宫问题数据结构代码C++

以下是使用邻接矩阵存储迷宫的示例代码，以及广度优先搜索算法的实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 定义迷宫的邻接矩阵
vector<vector<int>> maze = {{1, 1, 1, 1, 1},
                            {0, 0, 1, 0, 0},
                            {1, 1, 1, 0, 1},
                            {1, 0, 0, 0, 1},
                            {1, 1, 1, 1, 1}};

// 定义起点和终点的坐标
pair<int, int> start = {1, 0};
pair<int, int> end = {3, 4};

// 定义广度优先搜索算法
bool bfs(vector<vector<int>> maze, pair<int, int> start, pair<int, int> end) {
    queue<pair<int, int>> q;
    set<pair<int, int>> visited;
    q.push(start);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        if (node == end) {
            return true;
        }
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            int x = node.first, y = node.second;
            vector<pair<int, int>> neighbors = {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
            for (auto neighbor : neighbors) {
                int i = neighbor.first, j = neighbor.second;
                if (0 <= i && i < maze.size() && 0 <= j && j < maze[0].size() && maze[i][j] == 1) {
                    q.push(neighbor);
                }
            }
        }
    }
    return false;
}

// 测试
int main() {
    if (bfs(maze, start, end)) {
        cout << "找到了出口！" << endl;
    } else {
        cout << "迷宫没有出口！" << endl;
    }
    return 0;
}

以上代码中，邻接矩阵 `maze` 存储了迷宫的结构，其中 `1` 表示可以通行的格子，`0` 表示障碍格子。起点和终点的坐标分别为 `start` 和 `end`，使用广度优先搜索算法 `bfs` 在迷宫上寻找从起点到终点的最短路径，如果找到了出口，则返回 true，否则返回 false。在 C++ 中，使用 `vector` 来表示邻接矩阵，使用 `pair` 来表示坐标。