【2D前缀和】【2D差分】邮票网格

用邮票贴满网格图

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

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

覆盖所有 空 格子。 不覆盖任何 被占据 的格子。 我们可以放入任意数目的邮票。 邮票可以相互有 重叠 部分。 邮票不允许 旋转 。 邮票必须完全在矩阵 内 。 如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

m == grid.length n == grid[r].length 1 <= m, n <= 10^5 1 <= m * n <= 2 * 10^5 grid[r][c] 要么是 0 ，要么是 1 。 1 <= stampHeight, stampWidth <= 10^5

初步想法是遍历所有邮票大小的滑动窗口，检查是否整个窗口都不被占据，是则更新这个窗口内所有格子，最后再检查所有未被占据的格子是否均被更新过。这两个核心操作都必须是在\(O(1)\)才能避免TLE。

本质是二维区间查询与区间更新问题，可以使用前缀和、差分解决。

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int H, int W) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> s(m + 1, vector<int>(n + 1, 0));
        vector<vector<int>> d(m + 1, vector<int>(n + 1, 0));
        // prefix sum
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] = grid[i - 1][j - 1] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        // loop window
        for (int i = 0; i <= m - H; i++) {
            for (int j = 0; j <= n - W; j++) {        
                // query if occupied
                if (s[i + H][j + W] - s[i][j + W] - s[i + H][j] + s[i][j] == 0) {
                    // update difference
                    d[i][j] += 1;
                    d[i][j + W] -= 1;
                    d[i + H][j] -= 1;
                    d[i + H][j + W] += 1;
                }
            }
        }
        // query final value
        vector<vector<int>> res(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                res[i][j] = res[i][j - 1] + res[i - 1][j] - res[i - 1][j - 1] + d[i - 1][j - 1];
                if (res[i][j] == 0 && grid[i - 1][j - 1] == 0) return false;
            }
        }
        return true;
    }
};