[KOITP] 등산(Not Solved)

출처 : http://koitp.org/problem/SDS_PRO_1_7/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	1792	281 (16%)	189

문제

최근 출시된 오버워치가 지루해진 형석이는 등산이나 하기로 결정했다. 형석이는 산의 시작점부터 도착지점까지 산을 오르락~ 내리락~ 하면서 간다. 하지만 형석이는 몸이 허약하여, 하루동안 급변한 고도의 변화를 느끼면 어지러움과 함께, 구토를 하며 쓰러진다.

형석이는 이런 증상을 최소화하기 위해, 경로 중 가장 높은 지점과, 가장 낮은 지점의 고도차가 가장 작게 등산 경로를 정하려고 한다. 하지만 등산 준비로 바쁜 형석이는 당신에게 이 문제를 부탁하였다.

산은 N*N의 크기로 이루어져 있다. 형석이는 (1,1)을 시작점으로, (N,N)을 도착점으로 정하였다. 또한 형석이는 상, 하, 좌, 우의 인접한 칸으로 이동할 수 있다. 가능한 형석이의 등산 경로 중, 가장 높은 지점과 낮은 지점의 차가 최소가 되는 경우의 그 값을 구하여라.

시간제한: 1초

입력

첫째 줄에 N(2<=N<=100)이 주어진다. 다음 N개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 경로 중 고도의 최대와 최소의 차가 가장 작아질 때의 그 값을 출력하세요.

힌트

입력 예제

5
1 1 3 6 8
1 1 8 5 6
8 10 0 4 3
8 0 2 3 4
4 3 0 2 1

출력 예제

5