UPC-4170 - 打地鼠 - 暴力枚举

题解链接：

https://www.lucien.ink/archives/115/

---

题目链接：

http://exam.upc.edu.cn/problem.php?id=4170

---

题目：

题目描述

打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。 游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了，所以你改装了锤子，增加了锤子与地面的接触面积，使其每次可以击打一片区域。如果我们把地面看做m*n的方阵，其每个元素都代表一个地鼠洞，那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点：每次挥舞锤子时，对于这R*C的区域中的所有地洞，锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中，每个地洞必须至少有1只地鼠，且如果某个地洞中地鼠的个数大于1，那么这个地洞只会有1只地鼠被打掉，因此每次挥舞锤子时，恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密，因此在游戏过程中你不能旋转锤子（即不能互换 R和C）。 你可以任意更改锤子的规格（即你可以任意规定R和C的大小），但是改装锤子的工作只能在打地鼠前进行（即你不可以打掉一部分地鼠后，再改变锤子的规格）。你的任务是求出要想打掉所有的地鼠，至少需要挥舞锤子的次数。 由于你可以把锤子的大小设置为1*1，因此本题总是有解的。

输入

第一行包含两个正整数m和n； 下面m行每行n个正整数描述地图，每个数字表示相应位置的地洞中地鼠的数量。

输出

输出一个整数，表示最少的挥舞次数。

样例输入

3 3 1 2 1 2 4 2 1 2 1

样例输出

4

提示

对于30%的数据，m,n<=5 ；

对于60%的数据，m,n<=30 ；

对于100%的数据，1<=m,n<=100 ，其他数据不小于0，不大于10^5。

---

思路：

  因为规定每一锤下去不能有格子不存在地鼠，所以说只有当地鼠总数是锤子面积的倍数的时候这个锤子才可能砸完地鼠。因为数据量很小，直接枚举锤子的长宽，然后判断是否是可行解即可。

---

实现：

#include <bits/stdc++.h> const int maxn = 107; int map[maxn][maxn], tmp_map[maxn][maxn], m, n, total, ans = 0x3f3f3f3f; bool update(int r, int c) { memcpy(tmp_map, map, sizeof(map)); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (tmp_map[i][j]) { int tmp = tmp_map[i][j]; for (int p = i; p < i + r; p++) for (int q = j; q < j + c; q++) { if (tmp_map[p][q] < tmp) return false; tmp_map[p][q] -= tmp; } } return true; } int main() { // freopen("in.txt", "r", stdin); scanf("%d%d", &m, &n); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) scanf("%d", map[i] + j), total += map[i][j]; for (int r = m; r > 0; r--) for (int c = n; c > 0; c--) if (total % (r * c) == 0 && total / (r * c) < ans && update(r, c)) ans = total / (r * c); printf("%d\n", ans); return 0; }