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

import sys

lines = []
for line in sys.stdin:
    a = line.split()
    lines.append(a)

m = int(lines[0][1])
n = int(lines[0][0])
DP = [[0 for _ in range(n)] for _ in range(m)]
DP[m-1][n-1] = max(-int(lines[m][n-1]) + 1, 1)  # 血量不能少于1
for i in range(1, m+n-1):
    for j in range(i+1):
        if j <= m-1 and (i-j) <= n-1:
            row = (m-1) - j
            column = (n-1) - (i-j)
            if row == m - 1:
                DP[row][column] = max(DP[row][column+1] - int(lines[row+1][column]), 1)  # 血量不能少于1
            elif column == n - 1:
                DP[row][column] = max(DP[row+1][column] - int(lines[row+1][column]), 1)  # 血量不能少于1
            else:
                down = max(DP[row+1][column] - int(lines[row+1][column]), 1)  # 血量不能少于1
                right = max(DP[row][column+1] - int(lines[row+1][column]), 1)  # 血量不能少于1
                DP[row][column] = min(down, right)  # 初始血量至少是多少，所以用min

print(DP[0][0])