AcWing 275. 传纸条 python
原题链接
中等
作者:
申侠
,
2020-11-03 11:49:55
,
所有人可见
,
阅读 369
n,m = map(int,input().split())
f = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(m+n-1)]
g = []
for _ in range(n):
t = list(map(int, input().split()))
g.append(t)
for k in range(m+n-1):
for x1 in range(n):
for x2 in range(n):
y1 = k-x1
y2 = k-x2
if y1 >= 0 and y2 >= 0 and y1 <m and y2 <m:
w = g[x1][y1]
if y1 != y2 :
w += g[x2][y2]
f[k][x1][x2] = max(f[k][x1][x2], f[k-1][x1-1][x2] + w)
f[k][x1][x2] = max(f[k][x1][x2], f[k-1][x1-1][x2-1] + w)
f[k][x1][x2] = max(f[k][x1][x2], f[k-1][x1][x2-1] + w)
f[k][x1][x2] = max(f[k][x1][x2], f[k-1][x1][x2] + w)
print(f[m+n-2][n-1][n-1])