A13894 | Triangles
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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](https://cutt.ly/NhbjZ2l); 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$ .
- 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](https://cutt.ly/NhbjZ2l); 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$ .
输入格式
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$ .
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$ .
输出格式
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$ .
输入输出样例
输入 #1
5 3 000 122 001 2 57 75 4 0123 4012 3401 2340 1 9 8 42987101 98289412 38949562 87599023 92834718 83917348 19823743 38947912
输出 #1
4 4 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 9 6 9 9 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 49 49 49 49 15 0 30 42 42
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.
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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted