P16849 [GKS 2021 #D] Arithmetic Square

给定一个 $3 \times 3$ 的整数网格。记 $G_{i,j}$ 为网格中第 $i$ 行第 $j$ 列的整数，其中 $i$ 和 $j$ 从 $0$ 开始编号。网格正中间的整数 $G_{1,1}$ 缺失。请找出该正方形的行、列和对角线中，能形成等差数列的序列的最大数量。你可以用任意整数替换缺失的数字。 等差数列（也称算术序列）是指一个序列，其中相邻两项的差为常数。用数学术语表示，即 $a_n = a_{n-1} + d$，其中 $d$ 为公差。在本问题中，一个序列可以是某一行、某一列或某一条对角线上的 $3$ 个数。我们希望通过替换缺失值为某个整数，使得最终得到的序列集合中，等差数列的数量最大。 如果两个序列来自不同的行、列或对角线，则视为不同。例如，中间行的序列 $\{2, 4, 6\}$ 与顶行的序列 $\{2, 4, 6\}$ 将算作 $2$ 个序列，但同一行、列或对角线上的序列 $\{2, 4, 6\}$ 与 $\{6, 4, 2\}$ 只算作一个序列。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例由 $3$ 行组成。 每个测试用例的第一行包含 $3$ 个整数：$G_{0,0}$、$G_{0,1}$ 和 $G_{0,2}$。 每个测试用例的第二行包含 $2$ 个整数：$G_{1,0}$ 和 $G_{1,2}$。 每个测试用例的最后一行包含 $3$ 个整数：$G_{2,0}$、$G_{2,1}$ 和 $G_{2,2}$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在设置缺失元素后，网格的行、列和对角线所能生成的等差数列的最大可能数量。

在样例 #1 中，如果将缺失数字设为 $5$，则恰好有 $4$ 个等差数列。 - 主对角线：$[3, 5, 7]$ - 副对角线：$[-1, 5, 11]$ - 中间列：$[4, 5, 6]$ - 右列：$[11, 9, 7]$ 如果将缺失数字设为其他整数，则只会得到 $1$ 个等差数列。因此答案为 $4$。 在样例 #2 中，如果将缺失数字设为 $4$，则恰好有 $3$ 个等差数列。 - 副对角线：$[6, 4, 2]$ - 中间行：$[3, 4, 5]$ - 左列：$[4, 3, 2]$ 将缺失数字设为其他任何整数都会导致更少的等差数列，因此输出 $3$。 在样例 #3 中，如果将缺失数字设为 $9$，则所有可能的等差数列都成立。总共有 $8$ 个等差数列（每个都是 $[9, 9, 9]$），因此输出 $8$。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i, j$，$G_{i,j}$ 为整数。 **测试集 1** 对于所有 $i, j$，$|G_{i,j}| \le 50$。 **测试集 2** 对于所有 $i, j$，$|G_{i,j}| \le 10^9$。 翻译由 DeepSeek V4 Pro 完成