A1262 迷宫|收集星星

#include <bits/stdc++.h>
using namespace std;

// 迷宫|收集星星（A1262）
//
// 时间没有限制 ⇒ 能收集到的就是 S 所在连通块里的所有星星。
// 用 BFS 找出 S 的连通块，统计其中的 '*'。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> mp(n);
    int sx = -1, sy = -1;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
        for (int j = 0; j < m; j++) {
            if (mp[i][j] == 'S') { sx = i; sy = j; }
        }
    }

    vector<vector<char>> vis(n, vector<char>(m, 0));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    int ans = 0;
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (mp[x][y] == '*') ans++; // 出队的格子若是星星，就收集到了
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }

    cout << ans << "\n";
    return 0;
}