import sys
input = sys.stdin.readline
from heapq import heappush,heappop
INF = sys.maxsize
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def Djikstra(x):
DP = [INF]*N*M
hq = []
heappush(hq,(0,x))
while hq:
w,now = heappop(hq)
if DP[now] <= w:
continue
DP[now] = w
for next,w1 in graph[now]:
heappush(hq,(w+w1,next))
return DP[0]
N,M,T,D = map(int,input().split())
MAP = []
for i in range(N):
MAP.append([*map(lambda x:ord(x)-65 if x.isupper() else ord(x)-71,input().strip())])
graph = [[] for i in range(N*M)]
for y in range(N):
for x in range(M):
h = MAP[y][x]
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
h1 = MAP[y1][x1]
if abs(h-h1) <= T:
d = 1
if h1>h:
d = (h1-h)**2
graph[y*M+x].append((y1*M+x1,d))
DP = [INF]*N*M
hq = []
heappush(hq,(0,0))
while hq:
w,now = heappop(hq)
if DP[now] <= w:
continue
DP[now] = w
for next,w1 in graph[now]:
heappush(hq,(w+w1,next))
highest = []
for i in range(N*M):
if DP[i] < D:
highest.append((MAP[i//M][i%M],i))
highest.sort(reverse=True)
for h,i in highest:
if Djikstra(i)+DP[i] <= D:
print(h)
break
풀이는 쉬운데 의외의 실수가 많았던 문제.
알고리즘 자체는 매우 쉽다. 그냥 모든 지점에서 인접한 곳으로 갈 수 있으면 그래프를 만들고 다익스트라를 하면 된다.
그런데 이제 내가 실수했던 부분은,
1. 호텔로 다시 돌아와야한다는 것을 안읽음
2. 아스키코드에서 소문자는 대문자 바로 다음에 나오는것이 아님
이었다.
이 문제는 특이하게 굳이 높이를 숫자가 아니고 알파벳으로 줬는데, 나는 높이로 치환하기 위해서 아스키코드를 이용하였다. 그런데 자꾸 예제의 답이 잘못 나와서 알아보니 아스키코드에서 A~Z 다음에 바로 a가 나오는게 아니라 특수문자가 나온 다음에 a~z가 나온다는 것을 알게되었다.
오늘의 교훈) 아스키코드에서 소문자는 대문자 바로 다음이 아니다.