leetcode

0 class Solution {

1 inline int clamp(const int a, const int x, const int y) { return min(max(a, x), y); }

2

3 public:

4 vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k) {

5 int n = mat.size(), m = mat[0].size();

6 vector<vector<int>> dp(n, vector<int>(m, 0)), res(n, vector<int>(m, 0));

7

8 for (int i = 0, sum = 0; i < n; i++)

9 sum = dp[i][0] = mat[i][0] + sum;

10 for (int i = 0, sum = 0; i < m; i++)

11 sum = dp[0][i] = mat[0][i] + sum;

12 for (int i = 1; i < n; i++) {

13 for (int j = 1; j < m; j++) {

14 dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];

15 }

16 }

17

18 for (int i = 0; i < n; i++) {

19 for (int j = 0; j < m; j++) {

20 int x1 = clamp(i - k, 0, n - 1), y1 = clamp(j - k, 0, m - 1);

21 int x2 = clamp(i + k, 0, n - 1), y2 = clamp(j + k, 0, m - 1);

22 res[i][j] = dp[x2][y2];

23 if (x1 > 0) res[i][j] -= dp[x1 - 1][y2];

24 if (y1 > 0) res[i][j] -= dp[x2][y1 - 1];

25 if (x1 > 0 && y1 > 0) res[i][j] += dp[x1 - 1][y1 - 1];

26 }

27 }

28

29 return res;

30 }

31 };