Description

MineLayer 是一个类似于扫雷的益智游戏，在一个 $R$ 行 $C$ 列的网格上进行。网格中的每个格子要么有一个地雷，要么没有地雷。MineLayer 谜题由一个数字网格组成，每个数字表示该格子及其所有相邻格子中的地雷总数。因此，这些数字的范围是 $0$ 到 $9$。

MineLayer 的目标是根据给定的提示数字，推断出网格中地雷的分布方案。

下面是一个典型的 $3$ 行 $4$ 列的网格。左侧是原始地雷布局，右侧是谜题的提示数字。

由于可能存在多种解法，你的任务是编写一个程序，输出中间一行中最多可能有多少个地雷。行数总是奇数，并且保证每个谜题至少有一个解。

Input Format

第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 个测试用例。

每个测试用例的第一行包含两个用空格分隔的整数：$R$ 表示行数，$C$ 表示列数。$R$ 总是奇数。接下来的 $R$ 行，每行包含 $C$ 个用空格分隔的整数，表示该行的提示数字。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是满足条件的情况下中间一行最多可能有多少个地雷。

2
3 3
2 2 1
3 4 3
2 3 2
3 4
1 2 1 1
2 3 3 2
2 2 2 1

Case #1: 1
Case #2: 1

Hint

数据范围

• $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 翻译