leetcode做题笔记2132. 用邮票贴满网格图

给你一个?m x n?的二进制矩阵?grid?，每个格子要么为?0?（空）要么为?1?（被占据）。

给你邮票的尺寸为?stampHeight x stampWidth?。我们想将邮票贴进二进制矩阵中，且满足以下?限制?和?要求?：

1. 覆盖所有?空?格子。
2. 不覆盖任何?被占据?的格子。
3. 我们可以放入任意数目的邮票。
4. 邮票可以相互有?重叠?部分。
5. 邮票不允许?旋转?。
6. 邮票必须完全在矩阵?内?。

如果在满足上述要求的前提下，可以放入邮票，请返回?true?，否则返回?false?。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

思路一：差分数组

c++解法

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int n = grid.size(),m = grid[0].size();
        vector<vector<int>> pre(n+3,vector<int>(m+3,0));
        vector<vector<int>> dif(n+3,vector<int>(m+3,0));
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                pre[i+1][j+1] = pre[i][j+1]+pre[i+1][j]-pre[i][j]+grid[i][j];
            }
        }
        for(int i = 1;i+stampHeight-1<=n;i++)
        {
            for(int j = 1;j+stampWidth-1<=m;j++)
            {
                int nx = i+stampHeight-1,ny = j+stampWidth-1;
                if(pre[nx][ny]-pre[i-1][ny]-pre[nx][j-1]+pre[i-1][j-1]==0)
                {
                    dif[i][j]++;
                    dif[nx+1][j]--;
                    dif[i][ny+1]--;
                    dif[nx+1][ny+1]++;
                }
            }
        }
        for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
            {
                dif[i][j] += dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];
                if(!grid[i-1][j-1]&&!dif[i][j]) return false;
            }
        }
        return true;
    }
};