题解 | #收集金币#

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
int n,m,t,x,y,v,ans;
struct node{int val,t;};
node a[1010][1010];
int f[1010][1010];
struct Node{int x,y,t;};
queue<Node>q;
signed main() {
	IOS
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j].val;
            a[i][j].t=1e8;
        }
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>x>>y>>v;
        a[x][y].t=v;   
    }
    q.push({1,1,1});
    f[1][1]=a[1][1].val;
    while(q.size()){
        auto temp=q.front();q.pop();
        if(temp.t>n+m)break;   
        if(a[temp.x+1][temp.y].t>temp.t&&temp.x+1>=1&&temp.x+1<=n&&temp.y>=1&&temp.y<=m){
            if(f[temp.x][temp.y]+a[temp.x+1][temp.y].val>f[temp.x+1][temp.y]){
                            //剪枝，避免无效状态进入队列
                f[temp.x+1][temp.y]=f[temp.x][temp.y]+a[temp.x+1][temp.y].val;
                q.push({temp.x+1,temp.y,temp.t+1});
            }
        }
        if(a[temp.x][temp.y+1].t>temp.t&&temp.x>=1&&temp.x<=n&&temp.y+1>=1&&temp.y+1<=m){
            if( f[temp.x][temp.y]+a[temp.x][temp.y+1].val>f[temp.x][temp.y+1]){
                            //剪枝，避免无效状态进入队列
                f[temp.x][temp.y+1]=f[temp.x][temp.y]+a[temp.x][temp.y+1].val;
                q.push({temp.x,temp.y+1,temp.t+1});
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           ans=max(ans,f[i][j]);
    cout<<ans;
    return 0;
}