P13488 [GCJ 2008 Finals] Mine Layer
题目描述
MineLayer 是一个类似于扫雷的益智游戏，在一个 $R$ 行 $C$ 列的网格上进行。网格中的每个格子要么有一个地雷，要么没有地雷。MineLayer 谜题由一个数字网格组成，每个数字表示该格子及其所有相邻格子中的地雷总数。因此，这些数字的范围是 $0$ 到 $9$。
MineLayer 的目标是根据给定的提示数字，推断出网格中地雷的分布方案。
下面是一个典型的 $3$ 行 $4$ 列的网格。左侧是原始地雷布局，右侧是谜题的提示数字。
由于可能存在多种解法，你的任务是编写一个程序，输出中间一行中最多可能有多少个地雷。行数总是奇数，并且保证每个谜题至少有一个解。
输入格式
第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 个测试用例。
每个测试用例的第一行包含两个用空格分隔的整数：$R$ 表示行数，$C$ 表示列数。$R$ 总是奇数。接下来的 $R$ 行，每行包含 $C$ 个用空格分隔的整数，表示该行的提示数字。
输出格式
对于每个测试用例，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是满足条件的情况下中间一行最多可能有多少个地雷。
说明/提示
**数据范围**
- $1 \leq N \leq 50$。
- 保证每个谜题至少有一个解。
**小数据范围（4 分，测试点 1 - 可见）**
- $R = 3$ 或 $R = 5$。
- $3 \leq C \leq 5$。
**大数据范围（13 分，测试点 2 - 隐藏）**
- $R$ 是 $3$ 到 $49$ 之间的奇数。
- $3 \leq C \leq 49$。
由 ChatGPT 4.1 翻译