BFS C++ 代码

#include <bits/stdc++.h>
using namespace std;
int M, N;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
struct node {
    int x, y, step;
};

int main() {
    while (cin >> M >> N, M != 0 && N != 0) {
        vector<vector<char>> result(M, vector<char>(N));
        queue<node> q;
        int x = 0, y = 0; // 起点坐标
        // 读入迷宫
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                cin >> result[i][j];
                if (result[i][j] == '@') {
                    x = i;
                    y = j;
                }
            }
        }
        // 初始化 BFS
        q.push(node{x, y, 0}); // 起点步数为 0
        result[x][y] = '#'; // 标记起点为已访问

        bool founds = false; // 是否找到终点
        while (!q.empty()) {
            node top = q.front();
            q.pop();
            int xx = top.x;
            int yy = top.y;
            int step = top.step;

            // 到达终点
            if (result[xx][yy] == '*') {
                cout << step << endl; // 输出路径长度
                founds = true;
                result[xx][yy] = '#'; // 标记终点为已访问
                break;
            }

            // 访问邻居
            for (int i = 0; i < 4; i++) {
                int a = xx + dx[i];
                int b = yy + dy[i];

                // 检查边界和障碍物
                if (a < 0 || a >= M || b < 0 || b >= N || result[a][b] == '#') continue;

                // 如果不是终点，则标记为已访问
                if (result[a][b] != '*') {
                    result[a][b] = '#';
                }

                // 将新节点加入队列
                q.push(node{a, b, step + 1});
            }
        }

        // 如果未找到终点，输出 -1
        if (!founds) {
            cout << -1 << endl;
        }
    }
    return 0;
}