力扣每日一题：2132. 用邮票贴满网格图（2023-12-14）

力扣每日一题
题目：2132. 用邮票贴满网格图

日期：2023-12-14
用时：38 m 32 s
思路：使用前缀和＋差分，只是往常是一维，现在变二维了，原理差不多
时间：22ms
内存：98.24MB
代码：

class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int xl = grid.length;
        int yl = grid[0].length;

        // 前缀和
        int[][] sum = new int[xl+1][yl+1];
        for(int i=1;i<=xl;i++){
            for(int j=1;j<=yl;j++){
                sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+grid[i-1][j-1];
            }
        }

        // 差分
        int[][] cnt = new int[xl+2][yl+2];
        for(int xStart=stampHeight;xStart<=xl;xStart++){
            for(int yStart=stampWidth;yStart<=yl;yStart++){
                int xEnd = xStart-stampHeight+1;
                int yEnd = yStart-stampWidth+1;
                if(sum[xStart][yStart]+sum[xEnd-1][yEnd-1]-sum[xStart][yEnd-1]-sum[xEnd-1][yStart]==0){
                    cnt[xEnd][yEnd]++;
                    cnt[xStart+1][yStart+1]++;
                    cnt[xEnd][yStart+1]--;
                    cnt[xStart+1][yEnd]--;
                }
            }
        }

        // 判断单元格是否能放邮戳
        for(int i=1;i<=xl;i++){
            for(int j=1;j<=yl;j++){
                cnt[i][j] += cnt[i][j-1]+cnt[i-1][j]-cnt[i-1][j-1];
                if(grid[i-1][j-1]==0&&cnt[i][j]==0){
                    return false;
                }
            }
        }

        return true;
    }
}