1314. 矩阵区域和

解法一：前缀和

先对矩阵求前缀和，有了前缀和之后就可以根据四部分的值求出任一矩阵的区域和。
注意考虑边界问题和源矩阵和前缀和矩阵之前的坐标关系。

class Solution {
    // 行数
    private int row;
    // 列数
    private int col;
    public int[][] matrixBlockSum(int[][] mat, int K) {
        row = mat.length;
        col = mat[0].length;
        // preSum[i][j]表示源矩阵中以(0,0)为左上角, (i-1,j-1)为右下角的矩阵内所有元素之和
        // 多开空间防止边界问题
        int[][] preSum = getPreSum(mat);
        int[][] ans = new int[row][col];
        int[] pos;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                pos = getPosition(i, j, K);
                ans[i][j] = preSum[pos[2]][pos[3]] - preSum[pos[2]][pos[1]] - preSum[pos[0]][pos[3]]
                        + preSum[pos[0]][pos[1]];
            }
        }
        return ans;
    }
    /**
     * 求解算子对应前缀和矩阵的左上角和右下角坐标
     * @param x 算子在源矩阵中的行坐标
     * @param y 算子在源矩阵中的列坐标
     * @param k 算子规模
     * @return 算子对应前缀和矩阵的左上角和右下角坐标
     */
    private int[] getPosition(int x, int y, int k) {
        int[] pos = new int[4];
        // 左上角行列坐标
        pos[0] = Math.max(0, x - k);
        pos[1] = Math.max(0, y - k);
        // 右下角行列坐标
        pos[2] = Math.min(row, x + k + 1);
        pos[3] = Math.min(col, y + k + 1);
        return pos;
    }
    /**
     * 求解矩阵的前缀和, ans[i][j]表示源矩阵中以(0,0)为左上角, (i-1,j-1)为右下角的矩阵内所有元素之和
     * @param mat 源矩阵
     * @return 前缀和矩阵
     */
    private int[][] getPreSum(int[][] mat) {
        int[][] ans = new int[row + 1][col + 1];
        for (int i = 1; i <= row; ++i) {
            for (int j = 1; j <= col; ++j) {
                ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        return ans;
    }
}