#include <bits/stdc++.h> using namespace std; using ll = long long; // 结构体：存储每个方格的信息 struct g { ll w; // 当前方格的金币数量 ll v = 0; // 当前方格变成墙的回合数（初始为0表示不会变墙） }; const ll N = 1e3 + 5; g a[N][N]; // 二维数组：存储迷宫中每个方格的金币和变墙信息 ll f[N][N]; // 动态规划数组：f[i][j]表示到达(i,j)方格时能收集到的最大金币数 // 辅助函数：判断方格(i,j)在到达时是否已变成墙 // 逻辑：从(1,1)到(i,j)需要走 (i-1)+(j-1) = x+y-2 步（即第x+y-2回合到达） // 若该方格的变墙回合v ≤ 到达回合，则到达时已变成墙，返回true；否则返回false bool b(ll x, ll y, ll v) { if (v != 0 && (x + y - 2) >= v) { // 注意：原代码的abs多余，x+y-2本身非负 return true; // 已变成墙，不可通过 } else return false; // 未变墙，可通过 } int main() { ll n, m; cin >> n >> m; // 输入迷宫的行数n和列数m // 输入每个方格的金币数量，存入a[i][j].w for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) { cin >> a[i][j].w; } } ll t; cin >> t; // 输入变墙信息的条数t // 输入每条变墙信息：(x,y)方格在第v回合变成墙，存入a[x][y].v for (ll i = 1; i <= t; i++) { ll x, y; cin >> x >> y; cin >> a[x][y].v; } // 动态规划初始化：起点是(1,1)，初始金币为该方格的金币数 f[1][1] = a[1][1].w; ll res = f[1][1]; // res维护过程中能收集到的最大金币数（初始为起点金币） // 动态规划遍历：按行/列顺序遍历每个方格，计算到达该方格的最大金币数 for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= m; j++) { // 情况1：当前在第一行（只能从左侧方格(j-1)转移过来） if (i == 1) { if (f[i][j-1] == 0) continue; // 左侧方格未被到达过，无法转移 if (!b(i, j, a[i][j].v)) { // 当前方格未变墙，可通过 f[i][j] = f[i][j - 1] + a[i][j].w; // 继承左侧的金币 + 当前方格金币 res = max(res, f[i][j]); // 更新最大金币数 } continue; } // 情况2：当前在第一列（只能从上方方格(i-1)转移过来） if (j == 1) { if (f[i-1][j] == 0) continue; // 上方方格未被到达过，无法转移 if (!b(i, j, a[i][j].v)) { // 当前方格未变墙，可通过 f[i][j] = f[i-1][j] + a[i][j].w; // 继承上方的金币 + 当前方格金币 res = max(res, f[i][j]); // 更新最大金币数 } continue; } // 情况3：非第一行/列（可从上方(i-1,j)或左侧(i,j-1)转移，取最大值） if (!b(i, j, a[i][j].v)) { // 当前方格未变墙，可通过 // 若上方和左侧都未被到达，无法转移，跳过 if (f[i-1][j] == 0 && f[i][j - 1] == 0) continue; // 取上方/左侧的最大金币数 + 当前方格金币 f[i][j] = max(f[i-1][j] + a[i][j].w, f[i][j - 1] + a[i][j].w); res = max(res, f[i][j]); // 更新最大金币数 } } } cout << res; // 输出能收集到的最大金币数 return 0; }