[SDOI 2011] 打地鼠

题目大意

n×mn \times m 的网格上打地鼠,每个格子上有 ai,ja_{i, j} 只地鼠。使用一种特殊的锤子,大小为 r×cr \times c,不能旋转,每次砸下去会打掉范围内每个格子恰好一只地鼠,打之前范围内不能有格子没有地鼠,锤子的大小只在游戏开始前设定好,游戏中无法改变。求最少的敲击次数。

1n,  m1001 \leqslant n, \; m \leqslant 100

0ai,  j100,0000 \leqslant a_{i, \; j} \leqslant 100,000

题目链接

【SDOI 2011】打地鼠 - Luogu 2484

题解

枚举锤子大小进行判断。

判断时,枚举要砸下去的左上角,整个范围内减去左上角的地鼠数(因为左上角的格子在枚举过程中,最后一次被覆盖到就是成为左上角时),当减出负数时失败。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <climits>
#include <algorithm>
const int MAXN = 105;
int n, m, mat[MAXN][MAXN];
bool check(int r, int c) {
static int temp[MAXN][MAXN];
for (int i = 1; i <= n; i++) std::copy(mat[i] + 1, mat[i] + m + 1, temp[i] + 1);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
if (!temp[i][j]) continue;
if (i + r - 1 > n && j + c - 1 > m) return false;
int t = temp[i][j];
for (int x = i; x < i + r; x++) for (int y = j; y < j + c; y++) {
temp[x][y] -= t;
if (temp[x][y] < 0) return false;
}
}
return true;
}
int main() {
scanf("%d %d", &n, &m);
int sum = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
scanf("%d", &mat[i][j]), sum += mat[i][j];
int ans = INT_MAX;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
if (sum % (i * j) == 0 && sum / (i * j) < ans && check(i, j)) ans = sum / (i * j);
}
printf("%d\n", ans);
return 0;
}