用c++写一段使用广度优先算法实现迷宫寻找路径的函数

在C++中使用广度优先搜索算法（Breadth-First Search, BFS）解决迷宫寻找路径的问题，首先需要定义迷宫的数据结构，通常可以使用二维数组来表示迷宫，其中0代表可通行区域，1代表障碍物。然后需要定义一个队列来存储待访问的节点，并使用标记数组来记录路径。下面是一个使用广度优先搜索算法实现迷宫寻找路径的示例函数：

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

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

// 方向数组，用于表示上下左右四个方向
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 检查位置(x, y)是否可以访问
bool isValid(int x, int y, std::vector<std::vector<int>>& maze) {
    return (x >= 0) && (x < ROW) && (y >= 0) && (y < COL) && maze[x][y] == 0;
}

// 使用BFS算法寻找迷宫路径的函数
bool findPath(std::vector<std::vector<int>>& maze, int startX, int startY, int endX, int endY) {
    if (maze[endX][endY] == 1 || maze[startX][startY] == 1) {
        return false; // 起点或终点有障碍物
    }
    
    // 创建一个同样大小的二维数组来记录路径
    std::vector<std::vector<bool>> visited(ROW, std::vector<bool>(COL, false));
    // 创建一个同样大小的二维数组来记录每个位置的前驱节点
    std::vector<std::vector<int>> prev(ROW, std::vector<int>(COL, -1));
    // 创建一个队列用于BFS
    std::queue<std::pair<int, int>> q;
    
    // 将起点加入队列，并标记为已访问
    q.push({startX, startY});
    visited[startX][startY] = true;
    
    // BFS主循环
    while (!q.empty()) {
        std::pair<int, int> curr = q.front();
        q.pop();
        
        // 如果到达终点，则返回true
        if (curr.first == endX && curr.second == endY) {
            return true;
        }
        
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int newX = curr.first + dir[i][0];
            int newY = curr.second + dir[i][1];
            
            // 如果新位置有效且未被访问
            if (isValid(newX, newY, maze) && !visited[newX][newY]) {
                q.push({newX, newY});
                visited[newX][newY] = true;
                prev[newX][newY] = curr.first * COL + curr.second; // 记录前驱节点
            }
        }
    }
    
    return false; // 没有找到路径
}

// 打印路径的函数
void printPath(std::vector<std::vector<int>>& prev, int endX, int endY) {
    if (prev[endX][endY] == -1) {
        std::cout << "No path found from " << startX << ", " << startY << " to " << endX << ", " << endY << std::endl;
        return;
    }
    
    std::vector<std::pair<int, int>> path;
    int curr = endX * COL + endY;
    
    // 回溯路径
    while (curr != -1) {
        path.push_back({curr / COL, curr % COL});
        curr = prev[curr / COL][curr % COL];
    }
    
    // 打印路径
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        std::cout << "(" << it->first << ", " << it->second << ") ";
    }
}

// 示例迷宫和起点终点
std::vector<std::vector<int>> maze = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

int main() {
    int startX = 0, startY = 0, endX = 4, endY = 4;
    if (findPath(maze, startX, startY, endX, endY)) {
        std::cout << "Path found from (" << startX << ", " << startY << ") to (" << endX << ", " << endY << "): ";
        printPath(maze, endX, endY);
    } else {
        std::cout << "No path exists." << std::endl;
    }
    return 0;
}

这个示例代码中，`findPath` 函数使用广度优先搜索算法来寻找迷宫中从起点到终点的路径。`printPath` 函数用于打印出找到的路径。在 `main` 函数中，我们定义了迷宫的起始点和终点，并调用 `findPath` 和 `printPath` 函数来展示搜索结果。