[USACO17OPEN] Modern Art P
题目描述
Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.
Picowso paints in a very particular way. She starts with an $N \times N$ blank canvas, represented by an $N \times N$ grid of zeros, where a zero indicates an empty cell of the canvas. She then draws $N^2$ rectangles on the canvas, one in each of $N^2$ colors (conveniently numbered $1 \ldots N^2$). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
She might then paint a rectangle in color 7:
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
And then she might paint a small rectangle in color 3:
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from $1 \ldots N^2$ is used exactly once, although later colors might completely cover up some of the earlier colors.
Given the final state of the canvas, please count how many of the $N^2$ colors could have possibly been the first to be painted.
小TY突然想画画，他有独特的艺术风格，他从N×N空白画布开始，其中0表示画布的空单元格。然后他会在画布上绘制恰好矩形，每个颜色是1到N×N中的一个。他每次可以选择任意一种未使用过的颜色进行绘画。例如，他可以从颜色2的矩形开始，画出这样的画布：
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
然后他可以用颜色7绘制一个矩形：
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
然后他可以在颜色3上绘制一个小矩形：
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
每个矩形都平行于画布边缘，而且矩形可以与整个画布一样大或者像一个单元一样小。每个颜色从1到正好使用一次，后来的颜色可能完全覆盖一些较早画上的颜色。
现在已知画布的最终状态，请计算有多少种颜色可能被第一个被画。
输入输出格式
输入格式
The first line of input contains $N$, the size of the canvas ($1 \leq N \leq 1000$).
The next $N$ lines describe the final picture of the canvas, each containing $N$ integers that are in the range $0 \ldots N^2$. The input is guaranteed to have been drawn as described above, by painting successive rectangles in different colors.
输出格式
Please output a count of the number of colors that could have been drawn first.
输入输出样例
输入样例 #1
4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0输出样例 #1
14说明
In this example, color 2 could have been the first to be painted. Color 3 clearly had to have been painted after color 7, and color 7 clearly had to have been painted after color 2. Since we don't see the other colors, we deduce that they also could have been painted first.
感谢@ yhf\_2015 的翻译