Modern Art
실버 II의견: 0
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.
Unfortunately, since Picowso has become so famous, her painting style is being
copied by many of her competitors. In fact, one competitor, Moonet, is trying
to make exact copies of Picowso's paintings!
Picowso is curious how long it will take to duplicate one of her paintings.
She figures that to do so, one could paint a collection of rectangles on the
canvas as long as they don't overlap (since overlapping would cause the paints
to mix). After waiting for these to dry, one could again paint a collection of
disjoint rectangles. This new set of rectangles can overlap the first set of
rectangles, since the first set is now dry. We proceed in this fashion, where
in each round we paint a set of disjoint rectangles and then wait for them to
dry. At most one rectangle of each color can be drawn during the entire
process, since otherwise the result would not be in the authentic Picowso style.
Please help determine the minimum number of rounds necessary to duplicate a
given Picowso painting.
Problem credits: Brian Dean
Problem credits: Brian Dean
The first line of input contains \(N\), the size of the canvas
(\(1 \leq N \leq 40\)). 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 the minimum number of rounds required to produce a duplicate of
the given painting.
art.inart.out4
2 2 3 0
2 7 3 7
2 7 7 7
0 5 5 53In this example, round one consists of drawing rectangles of colors 2 and 5.
Round two involves drawing the rectangle of color 7, and the third and final
round involves drawing the rectangle of color 3 (of course, the rectangle of
color 5 could have been drawn during rounds 2 or 3 also).
평가 및 의견
Modern Art
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Modern Art