BOJ - 1486 - 등산

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