Modern Art

题目描述

全世界的艺术评论家直到最近才开始认可伟大的牛类画家 Picowso 背后的创作天才。 Picowso 的作画方式非常独特。她从一块 $N \times N$ 的空白画布开始，将其表示为一个由 0 组成的 $N \times N$ 网格，其中 0 表示画布上的空格。接着，她在画布上画 $N^2$ 个矩形，每个矩形使用一种颜色，共 $N^2$ 种颜色（方便起见编号为 $1 \ldots N^2$）。例如，她可能先用颜色 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 \ldots N^2$ 中的每一种颜色都恰好使用一次，不过后画的颜色可能会将先画的颜色完全覆盖。 给定画布的最终状态，请统计这 $N^2$ 种颜色中，有多少种颜色可能是最先被画上去的。

输入格式

第一行输入为 $N$，表示画布的大小（$1 \leq N \leq 1000$）。 接下来的 $N$ 行描述画布的最终图案，每行包含 $N$ 个整数，范围为 $0 \ldots N^2$。 保证输入确实可以由上述过程得到：依次用不同颜色绘制矩形。

输出格式

请输出可能最先被绘制的颜色数量。

4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0

14

提示

在这个例子中，颜色 2 可能是最先被画上的。颜色 3 显然必须在颜色 7 之后画，颜色 7 显然必须在颜色 2 之后画。由于我们看不到其他颜色，我们推断它们也都可能是最先被画上的。 题目来源：Brian Dean

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum