若目标位于爆破正方形的边上,该目标将不会被摧毁。

这是题中给出的说明,但是按照这个要求取计算,不取正方形边界的数据,答案是错误的,包含边界的数据反而是正确的,所以归根结底就是一个简单的二维前缀和的问题。

但是重要的是,在标记最大行数和列数之前,xx 和 yy要初始化为r,因为最大边界至少要满足r的大小才能进行接下来的遍历,否则没有意义。

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
int a[N][N], s[N][N], n, r, xx, yy;

int main(){
    cin >> n >> r;
    xx = yy = r;//缺少这一步会错误 边界大小至少要满足正方形边长才能进行遍历
    while(n --){
        int x, y, v;
        cin >> x >> y >> v;
        a[x + 1][y + 1] = v;
        xx = max(xx, x + 1), yy = max(yy, y + 1);
    }

    //计算二维前缀和
    for(int i = 1; i <= xx; i ++)
        for(int j = 1; j <= yy; j ++)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];

    //计算区域最大值 不包括边界数据会错 题意有问题!!!!
    int ans = 0;
    for(int i = 1; i <= xx - r + 1; i ++)
        for(int j = 1; j <= yy - r + 1; j ++){
            int x = i + r - 1, y = j + r - 1;
            ans = max(ans, s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1]);
        }

    cout << ans;
}