1314. 矩陣區域和

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

---

解題思路

? 首先我們要明白題目要我們干什么，其實就是求出矩陣中每個元素，它向外拓展 k 個單位之后形成的區域的總和，如下圖中以元素 4 為例，如果 k = 1 的話的情況：

? 那其實這道題我們就可以用之前學過的二維前綴和來解決，大體思路都是一樣的，雖然我們給過模板，但是切記不要死記硬背，要理解模板是怎么來的！

? 下面的推導，統一使用以上圖中元素 4 為中心，k=1 的例子來推導！

? 還是一樣，首先我們需要一個二維的 dp 表來記錄前綴和，而 dp[i][j] 就表示從 [0, 0] 到 [i, j] 的元素總和。

? 根據狀態表示和區域的累加，可以得到 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i][j]，這個和模板題是類似的，這里就不細講了！

? 接著我們再創建一個二維數組 ret，用于記錄每個位置的區域和作為函數返回值的，此時和二維前綴和模板題不同的是，我們這次要求的區間需要我們自己去求出來，其實也不難，只要求出了要求的區域的左上角和右下角兩個坐標，就能得到這個區間的信息了，如下圖所示：

? 也就是說，我們要求出圖中的 x1、y1、x2、y2，但問題是，有可能這個區間的一部分是越界的，但是我們只要有效區間，所以我們需要做處理而不能單純的讓 x1 = 中心坐標 - k 這樣子去計算，會出錯的！

? 那么該如何靈活的計算這個可能越界的坐標情況呢???

? 其實非常簡單，首先假設中心元素 4 的坐標是 [i, j]，然后做法如下所示：

? 以左上角為例，如果 i