前缀和（八）矩阵区域和

 1314. 矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {// 1、初始化前缀和dp数组int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m+1, vector<int> (n+1));for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)   // dp前缀和数组定义为从[1,1]->[i,j]位置的和dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];// for(int i = 1; i <= m; i++)//     for(int j = 1; j <= n; j++)//         cout<<dp[i][j]<<" ";// 2、使用前缀和进行更新answervector<vector<int>> ans(m, vector<int> (n));int x1,y1,x2,y2;for(int i = 1; i <= m; i++){for(int j  = 1; j <= n; j++){x1 = i-k < 1 ? 1 : i-k;y1 = j-k < 1 ? 1 : j-k;x2 = i+k > m ? m : i+k;y2 = j+k > n ? n : j+k;ans[i-1][j-1] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];// cout<<ans[i-1][j-1];}}return ans;}
};