leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1314.cpp (1210B)

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 };