인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다.

여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.

세계를 N×N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 형태로 생각할 수 있다.

가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N)위치에 있다.

두 정사각형 (a,b)와 (a’, b’)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.

● |a - a’| = 1 이고 b = b’, ● |b - b’| = 1 이고 a = a’.

문명의 최초 발상지는 모두 서로 다른 K곳에 있다. 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다.

문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다.

한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다.

정사각형 (a,b)가 문명 지역이면, 다음 해에는 세계의 경계를 넘지 않는 한

이 정사각형과 인접한 네 정사각형 (a+1,b), (a-1,b), (a,b+1), (a,b-1)에 문명이 전파된다.

만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.

예를 들어, 다음과 같이 5×5 크기의 세계에 4곳의 정사각형 (1,1), (2,1), (2,5), (5,2)가 문명의 발상지라고 하자.

정사각형 (1,1), (2,1)의 문명은 인접해 있으므로 처음부터 결합되어 있다.

1년 후 문명이 전파된 지역은 오른쪽 그림과 같고, 2년 후에 문명이 전파된 지역은 아래 그림과 같다.

이때 모든 문명은 서로 결합되어 하나의 문명이 된다.

(2,5)에서 발상한 문명과 (5,2)에서 발상 한 문명은 직접적으로 결합되지는 않았지만, (1,1), (2,1)에서 발상한 문명을 통하여 결합됨에 주의하라.

세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.

문명 timer 1s memory 256MB

문명 1s 256MB