시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 538 112 58 15.263%

문제

세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다.

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다.

세준이의 호텔은 (0,0)에 위치해 있다. 그리고, 세준이는 지금위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다.

만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이가 5에서 높이가 9인 곳으로 간다면, 시간은 (5-9)^2=16이 걸린다. 하지만, 높이가 9인 곳에서 5인 곳으로 간다면 시간은 1이 걸린다.

산의 지도와, T, 그리고 어두워지는 시간 D가 주어졌을 때, 세준이가 D보다 크지 않은 시간동안 올라갈 수 있는 최대 높이를 구하는 프로그램을 작성하시오.(세준이는 호텔에서 출발해서 호텔로 돌아와야 한다.)

입력

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 갈 수 있는 가장 높은 곳의 위치를 출력한다.

예제 입력

6 6 6 36
AABCDE
GJIHGF
MKLMNO
STSRQP
YUVWXY
edcbaZ

예제 출력

30

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: dtc03012