#PU744. USACO 2017 US Open Contest, Platinum — Problem 1. Modern Art

    ID: 1586 传统题 文件IO:art 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open17来源:usaco.orgscoring:equal_test_cases枚举

USACO 2017 US Open Contest, Platinum — Problem 1. Modern Art

USACO 2017 US Open Contest, Platinum — Problem 1. Modern Art

题目描述

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×NN \times N blank canvas, represented by an N×NN \times N grid of zeros, where a zero indicates an empty cell of the canvas. She then draws N2N^2 rectangles on the canvas, one in each of N2N^2 colors (conveniently numbered 1…N21 \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…N21 \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 N2N^2 colors could have possibly been the first to be painted.

输入格式

The first line of input contains NN, the size of the canvas (1≤N≤10001 \leq N \leq 1000). The next NN lines describe the final picture of the canvas, each containing NN integers that are in the range 0…N20 \ldots N^2. The

输出格式

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
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.
Problem credits: Brian Dean