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

题目描述

小 D 穿越到《超级泡泡堂》世界，需要在地图上选择一个位置（即他当前所在位置）放置唯一一次可用的炸弹。炸弹爆炸后，火焰会向上下左右四个方向蔓延：

• 遇到空地（.）可继续传播；
• 遇到杂草（!）会将其烧毁（计为 1 个被清除的杂草）并继续传播；
• 遇到石头（#）或地图边界则停止该方向传播。

目标是计算最多能烧掉多少杂草。

本题是考察连通性搜索（DFS/BFS） 的题，难度中等

核心思路

核心观察

火焰的蔓延规则等价于：从起始点出发，在不穿过石头的前提下，遍历所有可达的格子（包括空地和杂草），其中每个 ! 贡献 1 点答案。
由于技能只能用一次且必须在当前位置使用，因此问题转化为：从起点 @ 出发，能到达的所有非石头格子中，有多少个是杂草 !？

算法步骤

1. 读入地图，记录起点 @ 的坐标 (x, y)；
2. 将石头 # 标记为不可访问（在 visited 中预设为 true）；
3. 将杂草 ! 在 graph 中记为 1，空地 . 和起点记为 0；
4. 从起点 (x, y) 开始进行深度优先搜索（DFS）或广度优先搜索（BFS）：
   • 跳过越界或已访问（含石头）的位置；
   • 累加当前格子的值（0 或 1）；
   • 递归/迭代探索四个方向；
5. 输出累加结果，即最多可烧毁的杂草数量。

正确性分析

• 火焰传播具有传递性和无后效性：一旦某个格子被火焰到达，其后续传播与路径无关，仅取决于该格子类型。
• DFS/BFS 能完整遍历所有从起点可达的非石头格子，不会遗漏也不会重复（通过 visited 保证）。
• 每个杂草 ! 被访问时恰好被计数一次，符合题目要求。

复杂度分析

• 时间复杂度：
  • 每个格子最多被访问一次，总操作次数与地图大小成正比。
• 空间复杂度：
  • 使用了两个 的二维数组 graph 和 visited 存储地图状态和访问标记；递归 DFS 的栈深度最坏为 （如蛇形路径），但通常可接受。

参考代码

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m, N = 2026;
vector<vector<int>> graph(N, vector<int>(N, 0));
vector<vector<bool>> visited(N, vector<bool>(N, false));

int dfs(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)return 0;
    if (visited[x][y])return 0;

    int res = graph[x][y];
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        res += dfs(xx, yy);
    }
    return res;
}

int main() {
    int x, y;
    cin >> n >> m;


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if (c == '.')graph[i][j] = 0;
            else if (c == '#')visited[i][j] = true;
            else if (c == '!')graph[i][j] = 1;
            else x = i, y = j;
        }
    }

    cout << dfs(x, y);
}