CF1453C.Triangles

Gildong has a square board consisting of $n$ rows and $n$ columns of square cells, each consisting of a single digit (from $0$ to $9$). The cell at the $j$-th column of the $i$-th row can be represented as $(i, j)$, and the length of the side of each cell is $1$. Gildong likes big things, so for each digit $d$, he wants to find a triangle such that:

• Each vertex of the triangle is in the center of a cell.
• The digit of every vertex of the triangle is $d$.
• At least one side of the triangle is parallel to one of the sides of the board. You may assume that a side of length $0$ is parallel to both sides of the board.
• The area of the triangle is maximized.

Of course, he can't just be happy with finding these triangles as is. Therefore, for each digit $d$, he's going to change the digit of exactly one cell of the board to $d$, then find such a triangle. He changes it back to its original digit after he is done with each digit. Find the maximum area of the triangle he can make for each digit.

Note that he can put multiple vertices of the triangle on the same cell, and the triangle can be a degenerate triangle; i.e. the area of the triangle can be $0$. Also, note that he is allowed to change the digit of a cell from $d$ to $d$.

吉尔东有一块 $n$ 行 $n$ 列的正方形棋盘，每个格子为一个单位正方形，其中填有一个数字（从 $0$ 到 $9$）。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$，每个格子边长为 $1$。吉尔东喜欢大的东西，因此对每个数字 $d$，他希望找出一个三角形，满足以下条件：

• 该三角形的每个顶点都位于某个格子的中心；
• 每个顶点所在格子中的数字均为 $d$；
• 该三角形至少有一条边与棋盘的某条边平行（可假设长度为 $0$ 的边与棋盘的两条边均平行）；
• 该三角形的面积尽可能大。

当然，他不会仅仅满足于直接找出这些三角形。因此，对每个数字 $d$，他将恰好修改棋盘上一个格子的数字为 $d$，然后在修改后的棋盘上寻找满足上述条件的三角形；在处理完该数字 $d$ 后，他再将该格子恢复为原来的数字。请对每个数字 $d$，求出他所能构造出的最大三角形面积。

注意：三角形的多个顶点可以位于同一个格子中心，且该三角形可以是退化三角形（即面积可为 $0$）。此外，他允许将一个原本就为 $d$ 的格子再次修改为 $d$（即不改变其值）。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

The first line of each test case contains one integer $n$ ($1 \le n \le 2000$) — the number of rows and columns of the board.

The next $n$ lines of each test case each contain a string of $n$ digits without spaces. The $j$-th digit of the $i$-th line is the digit of the cell at $(i, j)$. Each digit is one of the characters from $0$ to $9$.

It is guaranteed that the sum of $n^2$ in all test cases doesn't exceed $4 \cdot 10^6$.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one line with $10$ integers. The $i$-th integer is the maximum area of triangle Gildong can make when $d = i-1$, multiplied by $2$.

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

In the first case, for $d=0$, no matter which cell he chooses to use, the triangle with vertices at $(1, 1)$, $(1, 3)$, and $(3, 1)$ is the biggest triangle with area of $\cfrac{2 \cdot 2}{2} = 2$. Since we should print it multiplied by $2$, the answer for $d=0$ is $4$.

For $d=1$, Gildong can change the digit of the cell at $(1, 3)$ into $1$, making a triangle with vertices on all three $1$'s that has an area of $2$.

For $d=2$, Gildong can change the digit of one of the following six cells into $2$ to make a triangle with an area of $\cfrac{1}{2}$: $(1, 1)$, $(1, 2)$, $(1, 3)$, $(3, 1)$, $(3, 2)$, and $(3, 3)$.

For the remaining digits (from $3$ to $9$), the cell Gildong chooses to change will be the only cell that contains that digit. Therefore the triangle will always be a degenerate triangle with an area of $0$.

In the third case, for $d=4$, note that the triangle will be bigger than the answer if Gildong changes the digit of the cell at $(1, 4)$ and use it along with the cells at $(2, 1)$ and $(4, 3)$, but this is invalid because it violates the condition that at least one side of the triangle must be parallel to one of the sides of the board.

在第一种情况下，当 $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$ 时，需注意：若 Gildong 将位置 $(1, 4)$ 处格子的数字改为 $4$，并联合位置 $(2, 1)$ 和 $(4, 3)$ 处的格子构成三角形，则该三角形面积将大于正确答案；但这种做法是非法的，因为它违反了“三角形至少有一条边必须与棋盘某一边平行”的条件。