用C++写一个迷宫BFS算法的代码并记录完整的路径

迷宫广度优先搜索（BFS）算法是一种用于在图中找到两个节点之间最短路径的算法。以下是使用C++实现的迷宫BFS算法，它可以找到从起点到终点的路径，并记录下完整的路径。

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

// 方向数组，分别表示上下左右四个方向
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 迷宫的行数和列数
const int ROW = 5;
const int COL = 5;

// 检查是否可以移动到坐标(x, y)
bool isValid(int x, int y, vector<vector<int>>& maze, vector<vector<bool>>& visited) {
    return (x >= 0) && (x < ROW) && (y >= 0) && (y < COL) && 
           maze[x][y] == 1 && !visited[x][y];
}

// BFS函数，找到从起点到终点的路径
bool BFS(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
    // 如果起点不可通行，则返回false
    if (maze[start.first][start.second] != 1) return false;

    // 初始化迷宫的访问状态
    vector<vector<bool>> visited(ROW, vector<bool>(COL, false));

    // 初始化队列，存储坐标和路径
    queue<pair<pair<int, int>, vector<pair<int, int>>>> q;
    q.push({start, {start}});

    while (!q.empty()) {
        auto front = q.front();
        q.pop();
        pair<int, int> curr = front.first;
        vector<pair<int, int>> path = front.second;

        // 检查是否到达终点
        if (curr == end) {
            // 输出路径
            for (auto p : path) {
                cout << "(" << p.first << ", " << p.second << ") ";
            }
            cout << endl;
            return true;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int x = curr.first + dx[i];
            int y = curr.second + dy[i];

            // 如果可以移动到新位置
            if (isValid(x, y, maze, visited)) {
                visited[x][y] = true;
                vector<pair<int, int>> newPath = path;
                newPath.push_back({x, y});
                q.push({{x, y}, newPath});
            }
        }
    }

    // 如果没有路径到达终点
    return false;
}

int main() {
    // 创建迷宫，1表示通道，0表示障碍物
    vector<vector<int>> maze = {
        {1, 0, 0, 0, 1},
        {1, 1, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 1, 1},
        {0, 0, 0, 1, 1}
    };

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

    // 调用BFS算法
    if (!BFS(maze, start, end)) {
        cout << "没有找到从起点到终点的路径" << endl;
    }

    return 0;
}

这段代码定义了一个5x5的迷宫，使用BFS算法从(0, 0)位置开始搜索到(4, 4)位置的路径。如果找到路径，程序会输出路径；如果没有找到路径，则输出相应的提示信息。