题解 | #龙与地下城游戏问题#

n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))
dp = [0] * m
dp[-1] = 1 if matrix[-1][-1] > 0 else -matrix[-1][-1] + 1
for i in range(m - 2, -1, -1):
    dp[i] = max(dp[i + 1] - matrix[-1][i], 1)
for i in range(n - 2, -1, -1):
    dp[-1] = max(dp[-1] - matrix[i][-1], 1)
    for j in range(m - 2, -1, -1):
        right = max(dp[j + 1] - matrix[i][j], 1)
        down = max(dp[j] - matrix[i][j], 1)
        dp[j] = min(right, down)
print(dp[0])