用c++写一个迷宫BFS算法的代码

在C++中实现迷宫问题的BFS（广度优先搜索）算法可以分为以下几个步骤：

1. 定义迷宫地图，通常用二维数组表示，0代表通路，1代表墙。
2. 定义一个队列用于存储路径中的节点。
3. 确定搜索方向，比如上下左右四个方向。
4. 从起点开始，将起点加入队列，并将起点的位置标记为已访问。
5. 循环执行以下操作，直到队列为空：
- 从队列中取出一个元素作为当前位置。
- 检查当前位置是否是终点，如果是，则返回路径。
- 如果不是终点，则将当前位置的所有未访问的邻居加入队列，并更新邻居的位置为已访问。
6. 如果队列为空还未找到终点，则表示没有路径。

下面是一个简单的迷宫BFS算法的C++代码示例：

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for std::pair

using namespace std;

// 定义方向数组，分别表示上下左右
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 检查给定的坐标(x, y)是否在迷宫内且未被访问
bool isValid(int x, int y, int n, int m, vector<vector<int>>& maze, vector<vector<bool>>& visited) {
    return (x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !visited[x][y]);
}

// 广度优先搜索算法，返回从起点到终点的路径长度，如果无法到达则返回-1
int BFS(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
    int n = maze.size();
    int m = maze[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, pair<int, int>>> q; // 队列中存储位置和前一个位置的信息
    q.push(make_pair(0, start)); // 将起点加入队列
    visited[start.first][start.second] = true;

    while (!q.empty()) {
        pair<int, pair<int, int>> front = q.front();
        q.pop();
        int dist = front.first;
        pair<int, int> pos = front.second;

        // 到达终点
        if (pos == end) {
            return dist;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int newX = pos.first + dir[i][0];
            int newY = pos.second + dir[i][1];

            if (isValid(newX, newY, n, m, maze, visited)) {
                visited[newX][newY] = true;
                q.push(make_pair(dist + 1, make_pair(newX, newY)));
            }
        }
    }

    return -1; // 如果无法到达终点
}

int main() {
    vector<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}
    };

    pair<int, int> start(0, 0); // 迷宫的起点
    pair<int, int> end(4, 4);   // 迷宫的终点

    int pathLength = BFS(maze, start, end);

    if (pathLength != -1) {
        cout << "Path found, length: " << pathLength << endl;
    } else {
        cout << "No path found." << endl;
    }

    return 0;
}

以上代码展示了如何使用BFS算法解决迷宫问题，并在主函数中使用了一个简单的迷宫实例。它会输出找到的路径长度，或者当没有路径时输出无法到达的信息。