시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 4578 | 1279 | 777 | 24.281% |
세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다.
세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 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
2 2 3 10000 AD JG
9
2 2 3 29 AD JG
6
7 4 5 14 BCDE AJKF AIHG AAAA AOMK AQSI ACEG
10
7 4 5 57 BCDE AJKF AIHG AAAA AOMK AQSI ACEG
18
1 7 3 1000 ABCDEFK
5
8 9 4 50 TRRVUXefk bSNMOWcff bRPNNQZip XSRUTVcfj WbZQPXZbV XdYSRWVOP feedVVcZR XhfdZZefg
28