若目标位于爆破正方形的边上,该目标将不会被摧毁。
这是题中给出的说明,但是按照这个要求取计算,不取正方形边界的数据,答案是错误的,包含边界的数据反而是正确的,所以归根结底就是一个简单的二维前缀和的问题。
但是重要的是,在标记最大行数和列数之前,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;
}