CF1453C Triangles

Gildong 有一个由 $n$ 行 $n$ 列方格组成的正方形棋盘，每个格子中有一个数字（$0$ 到 $9$ 之间）。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$，每个格子的边长为 $1$。Gildong 喜欢“大”的东西，所以对于每个数字 $d$，他想找到一个三角形，满足： - 三角形的每个顶点都在某个格子的中心。 - 三角形每个顶点所在的格子的数字都是 $d$。 - 至少有一条边与棋盘的某条边平行。你可以认为长度为 $0$ 的边与棋盘的两条边都平行。 - 三角形的面积最大。 当然，他不会仅仅满足于直接找这些三角形。因此，对于每个数字 $d$，他会将棋盘中恰好一个格子的数字改成 $d$，然后再找这样的三角形。每次操作后，他会把格子的数字改回原来的数字。请你求出对于每个数字 $d$，他能构造出的最大三角形面积。 注意，你可以让多个三角形顶点落在同一个格子上，三角形也可以是“退化三角形”（即面积为 $0$）。另外，你可以把一个格子的数字从 $d$ 改成 $d$。

每组测试数据包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$），表示棋盘的行数和列数。 接下来的 $n$ 行，每行包含一个长度为 $n$ 的数字字符串，没有空格。第 $i$ 行第 $j$ 个字符表示格子 $(i, j)$ 的数字。每个数字都是字符 $0$ 到 $9$ 之一。 保证所有测试用例中 $n^2$ 的和不超过 $4 \cdot 10^6$。

对于每个测试用例，输出一行 $10$ 个整数，第 $i$ 个整数表示当 $d=i-1$ 时，Gildong 能构造出的最大三角形面积乘以 $2$ 的结果。

在第一个样例中，对于 $d=0$，无论选择哪个格子，顶点在 $(1, 1)$、$(1, 3)$ 和 $(3, 1)$ 的三角形面积最大，为 $\cfrac{2 \cdot 2}{2} = 2$。由于需要输出面积乘以 $2$，所以 $d=0$ 的答案是 $4$。 对于 $d=1$，Gildong 可以将 $(1, 3)$ 的数字改为 $1$，用所有三个 $1$ 构造面积为 $2$ 的三角形。 对于 $d=2$，Gildong 可以将以下六个格子中的一个改为 $2$，构造面积为 $\cfrac{1}{2}$ 的三角形：$(1, 1)$、$(1, 2)$、$(1, 3)$、$(3, 1)$、$(3, 2)$、$(3, 3)$。 对于剩下的数字（$3$ 到 $9$），Gildong 只能将一个格子的数字改为该数字，因此三角形只能是退化三角形，面积为 $0$。 在第三个样例中，对于 $d=4$，注意如果将 $(1, 4)$ 的数字改为 $4$，再与 $(2, 1)$ 和 $(4, 3)$ 组合，三角形面积会更大，但这种情况不合法，因为没有一条边与棋盘的边平行。 由 ChatGPT 4.1 翻译