문제
인섭이는 산속에 있는 상수의 집을 방문하기로 했습니다.
산은 M*N 격자로 표현되고, 각 격자 안에서는 높이가 일정하다고 가정합니다.
인섭이는 (1,1)에서 시작해서 (M,N)에 있는 상수의 집으로 가야 합니다. 인섭이는 상, 하, 좌, 우 4방향으로만 이동이 가능합니다.
과학을 잘 하는 인섭이는 높은 곳으로 올라가면 산소가 줄어든다는 것을 알고 있습니다.
산소결핍증에 걸려 죽기 싫은 인섭이는 경로 상에서 가장 높은 점의 높이를 최소로 하고 싶어 합니다.
인섭이의 경로 중 가장 높은 점의 높이의 최솟값을 구해 주세요!
입력
첫째 줄에 행의 수 M과, 열의 수 N이 주어집니다. 다음 M개 행과 N개의 열에 숫자가 주어집니다.
i번째 줄의 j번째 숫자는 (i,j)의 높이를 말합니다.
<제약조건>
서브태스크 1 : M≤100. N≤100. 1≤모든 높이≤1,000. 전체의 데이터의 50%
서브태스크 2 : M≤700. N≤700. 1≤모든 높이≤100,000,000.
출력
(1,1)에서 (M,N)으로 가는 인섭이의 경로 중 가장 높은 높이의 최솟값을 출력합니다.
예제
5 5
1 1 1 1 2
4 4 4 4 2
2 1 2 2 1
2 9 2 8 4
1 3 2 2 2
2
힌트
출처
cki86201
로그인해야 코드를 작성할 수 있어요.