IOI 1999 day2 3- 공항 부지 찾기(A Strip of Land) > 문제은행 : 정보올림피아드&알고리즘




2035 : 공항 부지 찾기(A Strip of Land)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
41 회   

문제

정올시  시민들이 비행장을 건설하기 위한 부지를 찾으려고 한다. 

정올시는 전체 모양이 직사각형 모양인데 도시 전체를 정사각형 격자로 구획을 나누어 관리하고 있다. 

공항 부지를 찾기 위하여 각 격자 구획에 해당 구획의 고도를 조사한 지도를 만들었다. 

공항 부지는 아래의 조건을 만족하면서 면적이 최대(즉, 정사각형 격자 구획을 가장 많이 차지하는)인 직사각형 영역으로 할 예정이다.


• 이 영역의 가장 높은 지역과 가장 낮은 지역의 높이 차이는 한계 치 C보다 작거나 같아야 한다.
• 이 영역의 너비(즉, 서-동 방향의 길이)는 최대 100 이다.


공항 부지를 나타내는 영역을 구하는 프로그램을 작성하시오.


입력형식

첫 행에 M, N, C가 입력된다. M은 격자 구획의 열 개수 이고 N은 행 개수 이다. C는 한계 치이다. (1 <= M, N <= 700, 0 <= C <= 10) 두 번째 행에서부터 N행에 걸쳐 N행 M열의 고도가 적힌 지도가 주어진다. 고도의 범위는 -30,000 ~ 30,000이다.

출력형식

하나의 행에 찾은 공항 부지의 왼쪽 아래 좌표와 오른쪽 위 좌표를 출력한다. 가장 왼쪽 아래 격자 구획의 좌표는 (1, 1)이고 가장 오른쪽 위 좌표는 (M, N)이다. 답이 여러 가지 경우가 나오는 경우 그 중 하나를 출력한다.

입력 예

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 48 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

출력 예

4 5 8 11

Hint!

입출력 예 설명



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP