레이팅 미적용전 세계 미술 평론가들은 최근에야 위대한 소 화가 피카우소의 창조적 천재성을 인정하기 시작했다.
피카우소는 매우 독특한 방식으로 그림을 그린다. 그녀는 \(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\)가지 색 중 가장 먼저 칠해졌을 가능성이 있는 색이 몇 개인지 세어 보자.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 캔버스의 크기 \(N\) (\(1 \leq N \leq 1000\))이 주어진다. 다음 \(N\)개의 줄에 캔버스의 최종 그림이 주어지며, 각 줄은 \(0 \ldots N^2\) 범위의 정수 \(N\)개로 이루어져 있다. 입력은 위에서 설명한 방식대로, 서로 다른 색의 직사각형들을 차례로 칠해서 그려진 것임이 보장된다.
가장 먼저 칠해졌을 가능성이 있는 색의 개수를 출력한다.
art.in · 출력을 쓸 파일 art.out4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 014In 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.
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > US Open > Platinum