算法竞赛模板

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

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

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

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

对网格每个被占据的地方求前缀和，然后遍历网格，如果没被占据查询前缀和数组判断贴下后会不会重合，能贴就贴上，最后差分数组求一次前缀和判断有没有空着的格子。

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int H, int W) {
        int n = grid.size();
        int m = grid[0].size();
        int fob[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                fob[i][j] = grid[i-1][j-1]; 
            }
        }
        for(int i = 0; i <= m; i++) fob[0][i] = 0;
        for(int i = 0; i <= n; i++) fob[i][0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                fob[i][j] += fob[i-1][j] + fob[i][j-1] - fob[i-1][j-1];
            }
        }
        int dif[n+2][m+2];
        memset(dif,0,sizeof(dif));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                int i2 = i + H - 1,j2 = j + W - 1;
                if(grid[i-1][j-1] == 0 && i2 <= n && j2 <= m) {
                    int cnt = fob[i2][j2] + fob[i-1][j-1] - fob[i2][j-1] - fob[i-1][j2]; 
                    if(cnt == 0) {
                        dif[i][j]++;
                        dif[i2+1][j2+1]++;
                        dif[i2+1][j]--;
                        dif[i][j2+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];
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(dif[i][j] == 0 && grid[i-1][j-1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
};