AlgoPressAppearance
1314-矩阵区域和
https://leetcode.cn/problems/matrix-block-sum
给你一个 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
基本思路 暴力解法
注意读懂题目， 目标矩阵 r,c 处的值，就是原来的矩阵处 mat[r][c] 的值，周围扩散 k 所有值的和。 先试一下暴力法，直接遍历，遍历到目标数组再循环周围的值相加，可能会超时(暴力法通过了)
参考代码
csharp
public class Solution {
protected int CalcSum(int[][] mat, int i, int j, int k){
int sum = 0;
for(int ii=i-k;ii<=i+k;ii++){
for(int jj = j-k; jj<=j+k;jj++){
//判断越界
if(ii>=0 && jj>=0 && ii<mat.Length && jj<mat[0].Length){
sum+=mat[ii][jj];
}
}
}
return sum;
}
public int[][] MatrixBlockSum(int[][] mat, int k) {
//初始化目标数组
int[][] answer = new int[mat.Length][];
for(int i=0;i<mat.Length;i++){
answer[i] = new int[mat[0].Length];
}
//计算和
for(int i=0;i<mat.Length;i++){
for(int j=0; j<mat[i].Length; j++){
answer[i][j] = CalcSum(mat,i,j,k);
}
}
return answer;
}
}
基本思路2: 【官方解法】 知识点 矩阵前缀和
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j]
扩展矩阵为 m+1,n+1, dp[i,j] = 表示从目前矩阵中到[i,j]所有数字的和 .png)
注意边界 dp[i+1][j+1] 表示 mat[i,j] 的前缀和， 在最后扣减前面前缀和的时候是扣减 mat[i-1][j-1] 所以最后代码中 左上边界，x1,x2直接使用，不需要+1，因为需要扣减1的 这个数组多扩展1圈的方法很好用。
csharp
public class Solution{
public int[][] MatrixBlockSum(int[][] mat, int k){
//初始化dp, 注意dp要扩展1个单位
int[][] dp = new int[mat.Length+1][];
int[][] answer = new int[mat.Length][];
for(int i=0;i<mat.Length+1;i++){
dp[i] = new int[mat[0].Length+1];
if(i<mat.Length){
answer[i] = new int[mat[0].Length];
}
}
//计算数组前缀和
for(int i=0;i<mat.Length;i++){
for(int j=0;j<mat[0].Length;j++){
//Console.WriteLine("i={0},j={1}",i,j);
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j];
}
}
//计算矩阵区域和(注意dp对应关系是+1)
for(int i=0;i<mat.Length;i++){
for(int j=0;j<mat[0].Length;j++){
int x1 = Math.Max(0,i-k);
int y1 = Math.Max(0,j-k);
int x2 = Math.Min(mat.Length-1,i+k);
int y2 = Math.Min(mat[0].Length-1,j+k);
//区域和 = 最终区域和 - 上面前缀和 - 左边前缀和 + 左上前缀和(注意左边和上边的边界不包含)
answer[i][j] = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1];
}
}
return answer;
}
}