题目详解

问题理解

我们有一个 $n \times m$ 的网格，包含：

• '.'：空单元格（可以放置炸药）
• 'g'：金矿石
• '#'：石头（无法放置炸药，但可能被爆炸影响）

炸药只能放在空单元格中。当在 $(x, y)$ 引爆时，以 $(x, y)$ 为中心、边长为 $2k+1$ 的正方形区域会被影响：

• 严格在正方形内部的金矿石会消失（损失）
• 在正方形边界上的金矿石会被收集

注意：爆炸可以超出网格边界，我们只关心网格内的金矿石。

---

关键观察

1. 多次爆炸可以收集所有剩余金矿石

考虑第一次爆炸后，位于爆炸正方形边界上的金矿石被收集，位于内部的金矿石消失。那么剩下的金矿石（未被第一次爆炸覆盖的）呢？

重要结论：我们可以通过后续的爆炸，收集所有剩余的金矿石。

方法：

• 第一次爆炸中心为 $(x, y)$，边长为 $2k+1$
• 第二次爆炸：在所有位于第一次爆炸正方形边界的空单元格上引爆
  • 这些爆炸的边长也是 $2k+1$，它们会覆盖第一次爆炸正方形边界附近的区域
• 第三次爆炸：在第二次爆炸正方形的边界上引爆
• 依此类推，直到覆盖整个网格

通过这种方式，除了第一次爆炸内部的金矿石外，其他所有金矿石都能被收集。

2. 问题转化

因此，最大化收集的金矿石 $\iff$ 最小化第一次爆炸损失的（即严格内部的）金矿石。

设：

• $total$ = 所有金矿石的总数
• $loss$ = 第一次爆炸正方形内部的金矿石数（不包括边界）
• 则答案 = $total - loss$

我们需要选择最优的第一次爆炸位置（必须在空单元格），使得 $loss$ 最小。

---

算法步骤

步骤 1：计算金矿石总数

遍历整个网格，统计 'g' 的个数，记为 $total$。

步骤 2：构建二维前缀和

为了快速计算任意矩形区域内金矿石的数量，我们构建二维前缀和数组 $sum$：

• $sum[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 的矩形内金矿石的数量
• 公式：$sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (grid[i-1][j-1] == 'g')$

步骤 3：枚举所有可能的第一次爆炸位置

对于每个空单元格 $(i, j)$（$0 \le i < n, 0 \le j < m$）：

• 爆炸正方形的边界范围：
  • 上边界：$i - k$
  • 下边界：$i + k$
  • 左边界：$j - k$
  • 右边界：$j + k$
• 爆炸正方形的内部（不包括边界）：
  • 行范围：$(i-k+1, i+k-1)$
  • 列范围：$(j-k+1, j+k-1)$
• 但在代码中，为了简化，先计算整个正方形的金矿石数（包括边界），再考虑边界处理。

代码实现细节：

int a = i - k, b = i + k + 1;  // b 是开区间右边界
int c = j - k, d = j + k + 1;
// pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c) 
// 计算的是 [a, b) × [c, d) 矩形内的金矿石数

这里 $a$ 和 $c$ 可能为负数，$b$ 和 $d$ 可能超过 $n, m$，但通过 check 函数将坐标裁剪到 $[0, n]$ 和 $[0, m]$ 范围内。

步骤 4：计算损失并更新答案

• 损失 = 第一次爆炸正方形内部的金矿石数
• 由于 pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c) 计算的是 $[a, b) \times [c, d)$ 内的金矿石数，这个区域正好是包含边界的正方形吗？

验证：

• 原始爆炸正方形边界：行从 $i-k$ 到 $i+k$，列从 $j-k$ 到 $j+k$
• 我们的区间：行 $[i-k, i+k+1)$，列 $[j-k, j+k+1)$
• 这正好是包含边界的整个正方形区域（包括边界上的格子）

但是题目要求：边界上的金矿石被收集，不算损失，只有严格内部的才算损失。

问题：代码直接用整个正方形的金矿石数作为损失，这正确吗？

仔细分析：

• 边界上的金矿石被收集，不应计入损失
• 严格内部的金矿石才会损失
• 但代码中并没有减去边界上的金矿石

重新审视：实际上，当 $k$ 减少 1 时，边长为 $2k+1$ 的正方形变为边长为 $2(k-1)+1 = 2k-1$ 的正方形，这正好是严格内部的区域。

代码中的处理：

k--;  // 一开始就 k--

然后在计算爆炸范围时：

int a = i - k, b = i + k + 1;

此时的 $k$ 已经减 1，所以实际计算的是边长为 $2k+1$ 的正方形？让我们检查：

设原始参数为 $K$，代码中 k-- 后 $k = K-1$。 爆炸正方形边长 $= 2k+1 = 2(K-1)+1 = 2K-1$。

而原始爆炸正方形的内部边长正好是 $2K-1$（因为外部边界宽度为 1）。

结论：代码通过 k-- 巧妙地直接计算了严格内部的金矿石数作为损失。

步骤 5：输出答案

答案 = $total - \min(loss)$

---

复杂度分析

• 时间复杂度：$O(n \cdot m)$ 对于每个测试用例
  • 计算前缀和：$O(n \cdot m)$
  • 枚举所有空单元格：$O(n \cdot m)$
• 空间复杂度：$O(n \cdot m)$

由于所有测试用例的 $n \cdot m$ 总和 $\le 2.5 \times 10^5$，完全可行。

---

示例验证

示例 1

2 3 1
#.#
g.g

$n=2, m=3, k=1 \to k' = 0$（内部区域边长为 1） 总金矿石 $total = 2$ 枚举空单元格：$(0,0)$ 和 $(0,2)$ 是石头，$(1,1)$ 是空 以 $(1,1)$ 为中心，内部区域仅包含 $(1,1)$ 本身（无金矿石） $\min(loss) = 0$ 答案 $= 2 - 0 = 2$

示例 2

2 3 2
#.#
g.g

$k=2 \to k' = 1$，内部区域边长为 3 以 $(1,1)$ 为中心，内部区域覆盖 $(0,0)$ 到 $(2,2)$，包含所有 2 个金矿石 $\min(loss) = 2$ 答案 $= 2 - 2 = 0$

示例 3

3 4 2
.gg.
g..#
g##.

总金矿石 = 4 最优爆炸位置可以最小化损失，最终得到 4

---

核心思想总结

1. 第一次爆炸的损失决定了最终能收集的金矿石数量
2. 通过后续爆炸可以收集所有剩余金矿石
3. 问题转化为：选择一个空单元格作为第一次爆炸中心，使得爆炸正方形内部的金矿石数最少
4. 使用二维前缀和快速计算任意矩形内的金矿石数
5. 通过 $k$ 减 1 的技巧直接计算内部区域