RiseOJ – 현대 미술

설명

전 세계 미술 평론가들은 최근에서야 위대한 소 화가 피카우소(Picowso)의 창조적 천재성을 알아보기 시작했다.

피카우소는 매우 독특한 방식으로 그림을 그린다. 그녀는 $N \times N$ 크기의 빈 캔버스에서 시작하는데, 이는 $N \times N$ 격자의 0들로 표현되며 0은 캔버스의 빈 칸을 나타낸다. 그런 다음 캔버스에 9개의 직사각형을 그리는데, 각각은 9가지 색(편의상 $1 \ldots 9$ 번) 중 하나로 칠한다. 예를 들어 먼저 색 2로 직사각형을 칠하면 다음의 중간 캔버스가 된다.

그다음 색 7로 직사각형을 칠할 수 있다.

그리고 색 3으로 작은 직사각형을 칠할 수 있다.

각 직사각형의 변은 캔버스의 변과 평행하며, 직사각형은 캔버스 전체만큼 클 수도 있고 한 칸만큼 작을 수도 있다. $1 \ldots 9$ 의 각 색은 정확히 한 번씩 사용되지만, 나중에 칠한 색이 먼저 칠한 색을 완전히 덮어 버릴 수도 있다.

캔버스의 최종 상태가 주어질 때, 캔버스에 아직 보이는 색들 중 가장 먼저 칠해졌을 가능성이 있는 색의 개수를 세시오.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 캔버스의 크기 $$N$$ 이 주어진다 ( $1 \leq N \leq 10$ ). 다음 $$N$$ 개의 줄은 캔버스의 최종 그림을 나타내며, 각 줄에 $0 \ldots 9$ 범위의 수 $$N$$ 개가 주어진다. 입력은 위에서 설명한 대로 서로 다른 색의 직사각형을 차례로 칠해 그려졌음이 보장된다.

출력 형식

최종 캔버스에 보이는 색들 중 가장 먼저 칠해졌을 가능성이 있는 색의 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 art.in · 출력을 쓸 파일 art.out

예제 1

입력

출력

설명

In this example, only 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.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > US Open > Bronze

올림피아드 > USACO > 2016-2017 > US Open > Bronze

태그

JudgeUSACO

현대 미술

평가 및 의견

풀이 제출