本文共 1843 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到两条路径，使得从左上角A点到右下角B点所经过的格子数之和最大。每个格子数只能被一个路径取走。

方法思路

我们可以使用动态规划来解决这个问题。具体来说，我们定义一个四维数组 f[i][j][k][l] 表示第一个路径走到格子 (i, j)，第二个路径走到格子 (k, l) 时的最大和。状态转移方程考虑了四种可能的情况：从左边和从上边分别来，或者从左边和从上边同时来。每种情况下，我们选择最大的前驱状态，并加上当前格子的值。如果两条路径走到同一个格子，则只加一次该格子的值。

解决代码

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    a = [[0]*(n+1) for _ in range(n+1)]
    while ptr < len(input):
        x = int(input[ptr])
        y = int(input[ptr+1])
        t = int(input[ptr+2])
        ptr += 3
        if x == 0 and y == 0 and t == 0:
            break
        a[x][y] = t
    # 初始化四维数组f，f[i][j][k][l]表示第一个到(i,j)，第二个到(k,l)的最大和
    f = [ [ [ [0]*(n+1) for _ in range(n+1) ] for __ in range(n+1) ] for ___ in range(n+1) ]
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                for l in range(1, n+1):
                    # 计算四个可能的前驱状态
                    p1 = f[i-1][j][k-1][l] if (i-1 >= 0 and j >= 1 and k-1 >= 0 and l >= 1) else 0
                    p2 = f[i-1][j][k][l-1] if (i-1 >= 0 and j >= 1 and k >= 1 and l-1 >= 0) else 0
                    p3 = f[i][j-1][k-1][l] if (i >= 1 and j-1 >= 0 and k-1 >= 0 and l >= 1) else 0
                    p4 = f[i][j-1][k][l-1] if (i >= 1 and j-1 >= 0 and k >= 1 and l-1 >= 0) else 0
                    p = max(p1, p2, p3, p4)
                    current = p + a[i][j]
                    if i != k or j != l:
                        current += a[k][l]
                    f[i][j][k][l] = current
    print(f[n][n][n][n])
if __name__ == "__main__":
    main()

代码解释

这种方法通过动态规划有效地解决了问题，确保了在有限的时间和空间复杂度内找到最优解。