Select solution language
Lời giải
Xoay ma trận 45 độ:
Mỗi ô (i,j) trong hệ tọa độ ban đầu được ánh xạ sang hệ mới: (X=i+j,Y=i−j+n)
Điều này giúp tất cả các ô có cùng tổng chỉ số X nằm trên cùng một đường chéo, giúp ta dễ dàng xác định phạm vi cộng dồn.
Prefix sum hai chiều:
Chúng ta tạo mảng prefix sum P để tính tổng nhanh với R là ma trận đã xoay 45 độ: P[x][y]=R[x][y]+P[x−1][y]+P[x][y−1]−P[x−1][y−1]
Sau đó, tổng giá trị trong phạm vi k của một ô (i,j) được tính như sau: sum(x1,y1,x2,y2)=P[x2][y2]−P[x1−1][y2]−P[x2][y1−1]+P[x1−1][y1−1]
Kết luận:
Code mẫu:
//CODE BY NHANZZZZ
#include <bits/stdc++.h>
using namespace std;
const int MX = 2005;
int n, k, a[1005][1005], r[MX][MX], p[MX][MX], res[1005][1005];
int sum(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return 0;
return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// nhap mang va xoay 45 do
cin >> n >> k;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> a[i][j];
int x = i + j, y = i - j + n;
r[x][y] = a[i][j];
}
}
// xay dung prefix sum hai chieu
for(int i = 1; i < MX; ++i){
for(int j = 1; j < MX; ++j){
p[i][j] = r[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
}
}
// tinh tong
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
int x = i + j, y = i - j + n;
int x1 = max(1, x - k), y1 = max(1, y - k);
int x2 = min(MX-1, x + k), y2 = min(MX-1, y + k);
res[i][j] = sum(x1, y1, x2, y2);
}
}
// in ket qua
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cout << res[i][j] << " ";
}
cout << "\n";
}
}