题解 | 收集金币

import sys
# 定义极大值
INF = 0x3f3f3f3f

def kkk():
    # 读取输入
    input_data = sys.stdin.read().split()
    ptr = 0
    
    # 读取行列数（n行m列）
    n = int(input_data[ptr])
    m = int(input_data[ptr+1])
    ptr += 2
    
    # 初始化网格（1-based索引，方便对标C++）
    # a[i][j] 对应原C++的a[N][N]，存储原始收益
    a = [[0]*(m+2) for _ in range(n+2)]  # 多开1列/行避免越界
    for i in range(1, n+1):
        for j in range(1, m+1):
            a[i][j] = int(input_data[ptr])
            ptr += 1
    
    # 初始化dp和cost数组（1-based）
    # dp[i][j]：从(1,1)走到(i,j)的最大收益，初始为-INF（不可达）
    dp = [[-INF]*(m+2) for _ in range(n+2)]
    # cost[i][j]：陷阱触发步数，初始为INF（无陷阱）
    cost = [[INF]*(m+2) for _ in range(n+2)]
    
    # 读取陷阱数量和陷阱信息
    t = int(input_data[ptr])
    ptr += 1
    for _ in range(t):
        x = int(input_data[ptr])
        y = int(input_data[ptr+1])
        v = int(input_data[ptr+2])
        ptr += 3
        cost[x][y] = v  # 记录陷阱触发步数
    
    # 处理陷阱：触发则将该位置收益设为-INF（不可达）
    for i in range(1, n+1):
        for j in range(1, m+1):
            step = i + j - 2  # 1-based步数计算
            if cost[i][j] <= step:
                a[i][j] = -INF
    
    # 边界初始化
    dp[1][0] = 0  # 第一行的左边界，方便j=1时取dp[i][j-1]
    dp[0][1] = 0  # 第一列的上边界，方便i=1时取dp[i-1][j]
    
    # 动态规划状态转移（1-based遍历）
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 取上方/左方的最大合法收益
            max_prev = max(dp[i-1][j], dp[i][j-1])
            # 仅当前驱路径合法时更新（避免-INF叠加导致溢出）
            if max_prev != -INF:
                dp[i][j] = max_prev + a[i][j]
    
    # 遍历所有位置取最大收益
    res = -1  
    for i in range(1, n+1):
        for j in range(1, m+1):
            if dp[i][j] > res:
                res = dp[i][j]
    
    # 输出结果（若所有路径都不可达，仍输出-1）
    print(res)

if __name__ == "__main__":
    kkk()