Informatica Online Judge

  춘추전국시대 [0788 / 0314]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 69   Total Tried : 86


The Champion of this Problem (C++) : wildsam - 3ms / 869byte
My Best Submission (C++) : N/A

[]

Background

넓은 대륙 하나로 이루어진 GS라는 세계에는 여러 국가들이 전쟁을 벌이고 있다.

유명한 전쟁분석가 경곽이는 이 세계에서 각 국가의 지배력이라는 수치를 이용하여 천하통일에 가장 가까운 국가와 곧 멸망할 국가를 찾아내려고 한다.

국가의 지배력은 그 국가의 상하좌우로 서로 연결된 영토의 넓이들을 각각 N1, N2, ... 이라고 했을 때 (Nk)^2의 합을 말한다(연결된 영토의 넓이가 각각 3,3,4라면 지배력은 9+9+16=34).

각 국가의 영토를 나타낸 지도가 주어질 때 가장 큰 지배력을 가진 국가와 가장 작은 지배력을 가진 국가를 구하는 프로그램을 작성하시오.

Input

입력파일의 첫 줄에 n, W, H가 주어진다( 2 <= n <= 500, 3 <= W, H <= 1000 ).

n은 국가의 수, W는 지도의 너비, H는 지도의 높이를 의미한다.

두 번째 줄부터 H+1 번째 줄까지 Ai( i = 1 ~ w , 0 <= Ai <= n )가 주어진다.

Ai는 그 지역이 어느 나라의 영토인지를 나타내며, 0인 경우 누구의 영토도 아닌 지역이다.

Output

가장 지배력이 높은 국가의 번호와 지배력, 낮은 국가의 번호와 지배력을 공백으로 구분하여 출력한다. 지배력이 같은 국가가 여러 개 있을 경우 번호가 가장 작은 국가를 출력한다.

IO Example

입력
3 5 4
0 1 1 2 2
1 1 3 2 2
1 3 3 2 3
0 1 0 3 3

출력
1 26 3 18

- 해설

1의 지배력은 5x5 + 1x1 = 26
2의 지배력은 5x5 = 25
3의 지배력은 3x3 + 3x3 = 18

따라서 최대 지배력은 26이고 국가는 1, 최소 지배력은 18이고 국가는 3이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]