Informatica Online Judge

  작물재배(Large) [1905 / 0771]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI Spring Training Camp Day1]

Background

경곽이는 지구의 오염으로 인하여 새로 발견한 행성으로 이주를 가기로 했다.

새로 발견한 행성은 R행과 C열의 격자로 이루어진 밭이 있다.

이 밭은 가로, 세로가 x, y축과 평행하다.

위로부터 i번째 행과 오른쪽으로부터 j번째 열을 좌표를 (i, j)로 나타낸다.

이 밭의 가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (R, C)다.

경곽이는 매년 밭에서 부는 바람의 방향을 상, 하, 좌, 우 중 하나로 설정한다.

경곽이는 이 밭에서 n개의 칸을 골라 작물을 재배하기로 했다.

이 작물은 바람에 따라서 영역을 확장해 나간다.

확장하는 방법은 매년 여름이 되면 설정된 바람의 방향으로 씨를 날린다.

날아간 씨는 정확하게 바람의 방향으로 한 칸 날아간 후 땅에 떨어진다.

그 영역이 외부로 벗어나지 않으면서, 아직 작물이 없었던 땅이라면 다음 해에 그 땅에 다시 새로운 작물이 자란다.

바람의 방향을 잘 설정하는 것으로 밭 전체에 작물이 자라도록 할 수 있다고 한다.

이 때 걸리는 최소 년수를 구하시오.

Input

첫 번째 줄에는 2개의 정수 R, C가 공백으로 구분되어 입력된다.

두 번째 줄에 정수 n이 주어진다.

다음 줄부터 n줄에 걸쳐서 작물이 위치한 좌표 (x, y) 한 줄에 하나씩 공백으로 구분되어 주어진다.

[입력값의 정의역]
1 <= n <= 300
1 <= r, c <= 1,000,000,000
처음 n개의 작물의 위치는 모두 다르다.

[Sub-Task Info]
#Tiny : 1 <= r, c <= 40
#Small : n <= 25
#Large : 추가제한사항 없음.

Output

밭 전체에 식물이 자리기 위해 필요한 최소 년수를 출력한다.

IO Example

입력
3 4
3
1 2
1 4
2 3

출력
3

* 설명
초기
- 0 - 0
- - 0 -
- - - -

1년 뒤
0 0 0 0
- 0 0 -
- - - -

2년 뒤
0 0 0 0
0 0 0 0
- 0 0 -

3년 뒤
0 0 0 0
0 0 0 0
0 0 0 0

따라서 3년만에 모두 채워진다.

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