C++ BFS算法实现迷宫最短路径

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PLL;
const int N = 110;
int n, m;
int g[N][N]; // 存放迷宫地图
int d[N][N]; // 每个点到起点的距离
PLL q[N*N]; // 模拟队列

int bfs()
{
    int hh = 0, tt = 0; // 定义队头和队尾
    q[0] = {0, 0}; // 定义起始位置
    memset(d, -1, sizeof d); // 初始化每个点为-1，表示未访问
    d[0][0] = 0; // 起点距离设为0
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 方向向量
    while (hh <= tt) // 队列不为空
    {
        auto t = q[hh++]; // 取出队头元素
        for (int i = 0; i < 4; i++) // 遍历四个方向
        {
            int x = t.first + dx[i], y = t.second + dy[i]; // 移动后的点
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) // 判断移动的合理性
            {
                d[x][y] = d[t.first][t.second] + 1; // 更新距离
                q[++tt] = {x, y}; // 将新节点加入队列
            }
        }
    }
    return d[n - 1][m - 1]; // 返回右下角(终点)的距离
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) // 读入迷宫地图
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    cout << bfs() << endl; // 输出最短路径长度
    return 0;
}

这段代码实现了使用BFS算法求解迷宫最短路径问题。它包含以下步骤：

初始化: 初始化队列、距离数组以及方向向量。
BFS搜索: 从起点开始，利用队列进行广度优先搜索，遍历所有可达的点，并更新每个点到起点的最短距离。
返回结果: 搜索结束后，返回终点到起点的最短距离。

这段代码清晰简洁，适合用于学习和理解BFS算法在求解最短路径问题上的应用。