广度优先搜索c++迷宫

下面是一个简单的 C++ 实现，使用广度优先搜索算法来解决迷宫问题。

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

const int MAX_N = 100; // 迷宫的最大行数和列数
int n, m; // 迷宫的行数和列数
char maze[MAX_N][MAX_N + 1]; // 表示迷宫的字符数组
int sx, sy; // 起点坐标
int gx, gy; // 终点坐标

int d[MAX_N][MAX_N]; // 到起点的最短距离的数组

// 移动的四个方向（上、右、下、左）
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

// 求从起点到终点的最短距离
int bfs()
{
    queue<pair<int, int>> q;
    // 初始化 d 数组为 -1（表示未到达过该点）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            d[i][j] = -1;
        }
    }
    // 把起点加入队列，并初始化到起点的最短距离为 0
    q.push(make_pair(sx, sy));
    d[sx][sy] = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        // 如果已到达终点，则结束搜索
        if (p.first == gx && p.second == gy) {
            break;
        }
        // 移动四个方向
        for (int i = 0; i < 4; i++) {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            // 如果移动后到达的位置是空地且未到达过（d[nx][ny]=-1），则加入队列，并更新到该位置的最短距离
            if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != '#' && d[nx][ny] == -1) {
                q.push(make_pair(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    // 返回从起点到终点的最短距离
    return d[gx][gy];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    // 在迷宫中寻找起点和终点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {
                sx = i;
                sy = j;
            }
            if (maze[i][j] == 'G') {
                gx = i;
                gy = j;
            }
        }
    }
    cout << bfs() << endl; // 输出从起点到终点的最短距离
    return 0;
}

以上是一个简单的广度优先搜索解决迷宫问题的 C++ 实现，可以根据需要进行修改和优化。