# BOJ - 1486 - 등산

Updated:

``````import sys
INF = 314152965
def solution():
N, M, T, D = map(int, sys.stdin.readline().split())

tmp = []
for _ in range(N):
tmp.append(list(str(sys.stdin.readline().strip())))

arr = [[0] * M for _ in range(N)]
floyd = [[INF] * (N * M) for _ in range(N * M)]
for r in range(N):
for c in range(M):
if 'A' <= tmp[r][c] <= 'Z':
arr[r][c] = ord(tmp[r][c]) - 65
else:
arr[r][c] = ord(tmp[r][c]) - 71

for i in range(N):
for j in range(M):
To = i * M + j
for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
if 0 <= i + dx < N and 0 <= j + dy < M:
From = M * (i + dx) + j + dy

start = arr[i][j]
end = arr[i + dx][j + dy]

if start - end > T or end - start > T:
floyd[To][From] = INF
elif start < end:
floyd[To][From] = (end - start) * (end - start)
else:
floyd[To][From] = 1

for k in range(N*M):
for i in range(N*M):
for j in range(N*M):
floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j])

ret = arr[0][0]
for i in range(N*M):
if floyd[0][i] + floyd[i][0] <= D:
ret = max(ret, arr[i // M][i % M])
print(ret)
solution()
``````

https://www.acmicpc.net/problem/1486

Categories:

Updated: