题目理解

我们有一个 $m \times n$ 的网格，每个格子有若干只地鼠。
我们可以选择一个固定的锤子尺寸 $R \times C$（不可旋转），然后在地图上进行若干次击打。
每次击打必须覆盖一个完整的 $R \times C$ 子矩形，且该子矩形内每个格子至少要有 $1$ 只地鼠。
每次击打会减少每个格子 $1$ 只地鼠（即所有格子地鼠数减 $1$）。
目标是用最少的击打次数清空地鼠。

关键观察

1. 锤子尺寸的影响
   锤子越大（$R \times C$ 越大），单次击打能打的地鼠越多（固定 $R \times C$ 只），但可能因为某些格子地鼠数量不足而无法在某些位置使用。

2. 可行性条件
   对于给定的 $R, C$，要想最终清空所有地鼠，必须满足：

   • 整个地图可以被分解成若干个不重叠的 $R \times C$ 矩形（实际上我们允许重叠击打，但这里等价于每个位置被覆盖的次数等于它的初始地鼠数）
   • 等价地，存在一种从左上到右下的贪心覆盖方式，使得所有格子在覆盖过程中不会出现负数。

3. 贪心覆盖策略
   对于固定的 $R, C$，我们从左上角 $(1,1)$ 开始，每次对当前子矩形 $[i, i+R-1] \times [j, j+C-1]$ 进行击打，次数等于该子矩形左上角 $(i,j)$ 位置剩余的地鼠数（因为必须把 $(i,j)$ 清空，且只能通过覆盖它的击打来减少）。
   然后更新该子矩形内所有格子的地鼠数。
   如果过程中出现某个格子的地鼠数变为负数，说明该 $R, C$ 不可行。

4. 为什么必须从左上到右下
   由于锤子覆盖的是右下方向的矩形，所以左上角的地鼠只能由覆盖它的最左上位置的击打来清除。因此顺序是固定的。

算法思路

1. 枚举所有可能的锤子尺寸

• $R$ 从 $1$ 到 $m$，$C$ 从 $1$ 到 $n$
• 对每个 $(R, C)$ 判断是否可行，并计算所需击打次数

2. 判断可行性与计算次数

• 复制地图到临时数组
• 从 $(1,1)$ 到 $(m-R+1, n-C+1)$ 遍历每个可能作为锤子左上角的位置 $(i,j)$
• 设 $need = \text{temp}[i][j]$（该位置剩余地鼠数）
• 如果 $need < 0$，说明不可行（之前过度击打）
• 如果 $need > 0$，则对以 $(i,j)$ 为左上角的 $R \times C$ 矩形每个格子减去 $need$
• 累加 $need$ 到总击打次数
• 遍历完后，检查整个地图是否全为 0（若有正数则不可行，因为无法再覆盖；若有负数则之前已判断）

3. 记录最小值

• 对所有可行的 $(R, C)$，记录最小的击打次数
• 由于 $1\times 1$ 总是可行（直接每个格子击打初始地鼠数次），答案总是存在

复杂度分析

• 枚举 $(R, C)$：$O(mn)$
• 对每个 $(R, C)$ 模拟：$O(mn \cdot RC)$ 最坏
• 总复杂度：$O(mn \cdot \sum_{R=1}^m \sum_{C=1}^n RC) = O(m^2 n^2 \cdot mn)$？
  实际上更紧的是 $O(mn \cdot m n \cdot mn)$？需要仔细算。

但 $m, n \leq 100$，最坏 $100^4 = 10^8$ 可能有点大，但实际由于 $R \leq m, C \leq n$，且内层循环不是满的，加上数据可能不强，可以通过。

样例分析

样例：

1 2 1
2 4 2
1 2 1

• 对于 $2\times 2$ 锤子：
  • 左上角 $(1,1)$ 有 1 只，击打 1 次 → 区域减 1 后：

    0 1 1
    1 3 2
    1 2 1
    

  • $(1,2)$ 有 1 只，击打 1 次：

    0 0 0
    1 2 1
    1 1 0
    

  • $(2,1)$ 有 1 只，击打 1 次：

    0 0 0
    0 1 0
    0 0 -1
    

  等等，这里出现负数，说明不能完全按这个顺序？
  实际上正确顺序是分别击打四个 $2\times 2$ 子矩形的左上、右上、左下、右下位置各 1 次，总 4 次。

这提示我们：在贪心时，必须保证每次击打时，矩形内所有格子剩余地鼠数都 ≥ 击打次数。
因此上面的贪心要修正为：击打次数 = 矩形内当前剩余地鼠的最小值（而不是左上角的值），但这样不一定最优？
实际上，题目要求每次击打时矩形内每个格子至少 1 只，所以击打次数不能超过矩形内最小值。
而为了清空左上角，击打次数至少为左上角的值。
所以取击打次数 = 左上角的值，但如果它大于矩形内最小值，则不可行。

总结

这道题的核心是：

1. 枚举所有锤子尺寸
2. 对每个尺寸用贪心模拟：从左上到右下，每次击打次数 = 当前矩形左上角的值，但要保证矩形内所有格子剩余地鼠数 ≥ 该值
3. 检查最终是否全清空，并记录最小击打次数

关键点在于理解锤子覆盖的约束和贪心顺序的合理性，通过枚举和模拟求解最优解。