파일 업로드

현대 예술

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

세계 각국의 미술 비평가들은 '비앙끄'로 알려진 훌륭한 화가 정숙의 창의성에 주목하기 시작했습니다.

정숙은 매우 특별한 방식으로 그림을 그립니다. 그녀는 처음에 N×NN \times N 크기의 빈 캔버스에 시작하는데, 이는 N×NN \times N 격자로 표현되며 각 셀에는 0이 들어가 있고, 이것은 공백 셀을 나타냅니다. 

그녀는 이후에 N2N^2개의 사각형을 캔버스 위에 그리는데, 각각 N2N^2개의 색상 중 하나로 그립니다 (편의상 1N21 \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

각 사각형은 캔버스의 모서리와 평행하며, 사각형의 크기는 전체 캔버스 크기만큼 클 수도 있고 하나의 셀만큼 작을 수도 있습니다. 1N21 \ldots N^2 범위의 각 색상은 정확히 한 번만 사용되며, 나중에 그린 색상들이 이전 색상들을 완전히 덮을 수 있습니다.

캔버스의 최종 상태가 주어진 경우, 첫 번째로 그려질 수 있었던 N2N^2 색상의 개수를 세십시오.

💻 입력
첫 번째 입력 줄에는 캔버스 크기 NN 이 있습니다 (1N10001 \leq N \leq 1000). 다음 NN 라인은 캔버스의 최종 그림을 묘사하며, 각각 0N20 \ldots N^2 범위의 NN 정수가 포함됩니다. 입력은 위에서 설명한대로 다른 색깔의 사각형을 차례대로 그리며 그려진 것으로 보장됩니다.
🖨️ 출력
첫 번째로 그려질 수 있었던 색깔의 수를 세어 출력하십시오.

💻 예제 입력 1
4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
🖨️ 예제 출력 1
14

💡 힌트
이 예시에서, 색깔 2는 첫 번째로 그려졌을 수 있습니다. 색깔 3은 분명 색깔 7 이후에 그려져야 했으며, 색깔 7은 분명 색깔 2 이후에 그려져야 했습니다. 우리가 다른 색들을 보지 못하기 때문에, 그들 또한 첫 번째로 그려졌을 수 있습니다.

출처: USACO 2017 US Open Contest, Platinum Problem 1. Modern Art