题解 | #小d和超级泡泡堂#

此问题本质上是一个图论中的连通性问题（Connectivity Problem），具体表现为二维网格图上的连通分量（Connected Component）计算。由于玩家的可达区域（移动）与火焰的覆盖区域（攻击）在拓扑结构上是完全重合的。问题转化为：计算包含起点（@）的“非石头”连通分量中，共有多少个杂草（!）。

由于我们需要在一个二维矩阵中找到一个连通区域并统计特定节点的数量，广度优先搜索 (BFS) 或 深度优先搜索 (DFS) 是标准且最优的解法。考虑到 可达 （总计 个节点），为了避免深层递归可能导致的栈溢出风险，基于队列的 BFS 或 迭代式 DFS 是更稳健的选择。

核心逻辑

1. 视为无向图：将矩阵看作一个图，每个坐标 (r, c) 是一个节点。如果两个相邻节点都不是石头，则它们之间存在边。
2. 单一源点遍历：只需从起点 (@) 触发一次遍历。
3. 统计目标：在遍历过程中，统计遇到的 ! 字符数量。
4. 状态记录：使用一个 visited 数组（或在原图标记）防止重复访问。

代码实现

该问题不需要复杂的动态规划或回溯，它是一个经典的图连通性（Flood Fill / 种子填充）问题。通过一次 BFS 遍历找到包含起点的非石头区域，并统计其中的杂草数量，即可得到最优解。

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

struct Point {
    int x;
    int y;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> mat(n);
    int startX, startY;
    for (int i = 0; i < n; i++) {
        cin >> mat[i];
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == '@') {
                startX = i;
                startY = j;
            }
        }
    }

    vector<vector<bool>> vis(n, vector<bool>(m, false));
    array<int, 4> dx{-1, 1, 0, 0};
    array<int, 4> dy{0, 0, -1, 1};

    queue<Point> Q;
    Q.push({startX, startY});
    vis[startX][startY] = true;

    int ans = 0;
    while (!Q.empty()) {
        auto [cx, cy] = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++) {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                continue;
            if (vis[nx][ny] || mat[nx][ny] == '#')
                continue;
            vis[nx][ny] = true;
            if (mat[nx][ny] == '!') {
                mat[nx][ny] = '.';
                ans++;
            }
            Q.push({nx, ny});
        }
    }

    cout << ans << endl;
}