编辑代码

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

#define MAX_N 100
#define MAX_M 100

const int INF = 100000000; // 1+9个0
typedef pair<int, int> P; // 重命名pair<int, int>
char maze[MAX_N][MAX_M + 1]; // 迷宫
int sx, sy; // 起点坐标
int gx, gy; // 终点坐标
int N, M; // 数组大小
int d[MAX_N][MAX_M]; // 起点到每个位置的最短距离
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // 四个方向移动的变量 (1, 0) (0, 1) (-1, 0) (0, -1) 右上左下

int bfs(); // 求(sx, sy) 到 (gx, gy)的最短距离 无法到达是INF
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> maze[i][j];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << maze[i][j] << "";
            if(maze[i][j] == 'G') {
                gx = i;
                gy = j;
            }
            if (maze[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
        cout << endl;
    }
    
    cout << bfs();
}

int bfs() {
    queue<P> que;
    // 将所有点初始化为INF
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            d[i][j] = INF;

    que.push(P(sx, sy)); // 起点加入队列 初始化距离为0
    d[sx][sy] = 0;

    // 不断循环直到队列的长度为0
    while (que.size()) {
        P p = que.front(); // 从队列前端取出元素
        que.pop();
        if (p.first == gx && p.second == gy)    break; // 如果取出来的点就是终点结束搜索

        // 四个方向循环
        for (int i = 0; i < 4; i++) {
            int nx = p.first + dx[i], ny = p.second + dy[i]; // 移动后的位置(nx, ny)

            // 判断移动后的位置没有越界 而且不是墙壁 而且从来没有到达
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {
                // 可以移动 就把这个点加入队列 然后这个位置到前一个点的距离+1
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gx][gy];
}