1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> res = mat, presum(m + 1, vector<int>(n + 1));
for (int r = 1; r <= m; ++r) {
for (int c = 1; c <= n; ++c) {
presum[r][c] = presum[r - 1][c] + presum[r][c - 1] - presum[r - 1][c - 1] + mat[r - 1][c - 1];
}
}
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
int ulr = max(0, r - K), ulc = max(0, c - K), brr = min(m - 1, r + K), brc = min(n - 1, c + K);
res[r][c] = presum[brr + 1][brc + 1] + presum[ulr][ulc] - presum[ulr][brc + 1] - presum[brr + 1][ulc];
}
}
return res;
}
};
|