Modern Art
提交数: 48, 通过率: 39.58%, 平均分: 68.13
题目描述:
modeArt critics worldwide have only recently begun to recognize the creative genius behind the great
bovine painter, Picowso.Picowso paints in a very particularway. She starts with an N×N blank canvas
, represented by an N×N grid of zeros, where a zero indicates an empty cell of the canvas. She then
draws N2 rectangles on the canvas, one in each of N2 colors (conveniently numbered 1…N2). For examp
le, 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 t
he entire canvas or as small as a single cell. Each color from 1…N^2is used exactly once, although
later colors might completely cover up some of the earlier colors.Given the final state of the canva
s, please count how many of the N^2colors could have possibly been the first to be painted.
给定一个n*n的矩阵，初始都为0，选择一个1到n*n的排列，然后按照这个排列的顺序，每次选择这个矩阵的一个非
空子矩形，然后涂上当前数字。现在给定最终的矩阵，求哪些数字可能是排列的第一位。
输入格式:
The first line of input contains N, the size of the canvas (1≤N≤1000). The next N lines describe t
he final picture of the canvas, each containing N integers that are in the range 0…N^2. The input i
s guaranteed to have been drawn as described above, by painting successive rectangles in different c
olors.
输出格式:
Please output a count of the number of colors that could have been drawn first.
样例输入:
4 2 2 3 0 2 7 3 7 2 7 7 7 0 0 0 0
样例输出:
14
提示:
In this example, color 2 could have been the first to be painted. Color 3 clearly had to have been p
ainted 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.
空间限制: 128MB
来源: Usaco2017 Open Platinum