1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

public static boolean possibleToStamp(int[][] grid, int h, int w) {
    int n = grid.length;
    int m = grid[0].length;
    
    // 构建前缀和数组，用于快速查询矩形区域的和
    // sum[i][j]表示从(0,0)到(i-1,j-1)的矩形区域累加和
    int[][] sum = new int[n + 1][m + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum[i + 1][j + 1] = grid[i][j];
        }
    }
    // 将sum转换为真正的前缀和数组
    build(sum);
    
    // 创建差分矩阵，用于高效记录邮票覆盖情况
    // 多开一圈是为了处理边界情况，避免数组越界
    int[][] diff = new int[n + 2][m + 2];
    
    // 遍历所有可能的邮票左上角位置(a,b)
    for (int a = 1, c = a + h - 1; c <= n; a++, c++) {
        for (int b = 1, d = b + w - 1; d <= m; b++, d++) {
            // (a,b)是左上角坐标(1-indexed)
            // (c,d)是右下角坐标，由邮票规格h×w计算得出
            // 如果这个区域的和为0，说明区域内全是空洞，可以贴邮票
            if (sumRegion(sum, a, b, c, d) == 0) {
                // 在差分矩阵中标记这次邮票覆盖操作
                add(diff, a, b, c, d);
            }
        }
    }
    
    // 对差分矩阵做前缀和还原，得到每个位置被覆盖的次数
    build(diff);
    
    // 检查原始网格中的所有空洞是否都被覆盖
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // grid[i][j] == 0表示这是一个空洞
            // diff[i + 1][j + 1] == 0表示这个空洞没有被任何邮票覆盖
            if (grid[i][j] == 0 && diff[i + 1][j + 1] == 0) {
                return false;
            }
        }
    }
    return true;
}

// 将矩阵原地转换为前缀和数组
// 转换后m[i][j]表示从(0,0)到(i,j)的矩形区域累加和
public static void build(int[][] m) {
    for (int i = 1; i < m.length; i++) {
        for (int j = 1; j < m[0].length; j++) {
            // 前缀和公式：当前值 = 原值 + 上方和 + 左方和 - 左上角和(减去重复计算部分)
            m[i][j] += m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1];
        }
    }
}

// 利用前缀和数组快速计算矩形区域(a,b)到(c,d)的累加和
public static int sumRegion(int[][] sum, int a, int b, int c, int d) {
    // 容斥原理：大矩形 - 上方矩形 - 左方矩形 + 左上角矩形(加回多减的部分)
    return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
}

// 差分数组操作：给矩形区域(a,b)到(c,d)整体加1
// 差分矩阵的核心：只修改四个角点，后续通过前缀和还原出整个矩形的覆盖情况
public static void add(int[][] diff, int a, int b, int c, int d) {
    diff[a][b] += 1;           // 左上角+1
    diff[c + 1][d + 1] += 1;   // 右下角外侧+1
    diff[c + 1][b] -= 1;       // 左下角外侧-1
    diff[a][d + 1] -= 1;       // 右上角外侧-1
}