给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
- 覆盖所有 空 格子。
- 不覆盖任何 被占据 的格子。
- 我们可以放入任意数目的邮票。
- 邮票可以相互有 重叠 部分。
- 邮票不允许 旋转 。
- 邮票必须完全在矩阵 内 。
如果在满足上述要求的前提下，可以放入邮票，请返回 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），它们能覆盖所有与空格子。
示例 2：
输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 输出：false 解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。
提示：
m == grid.lengthn == grid[r].length1 <= m, n <= 1051 <= m * n <= 2 * 105grid[r][c]要么是0，要么是1。1 <= stampHeight, stampWidth <= 105
方法一：二维前缀和 + 二维差分
根据题给的约束，很容易推出，一个格子能贴邮票的条件为，在加上邮票的长和宽后，右下角不越界的情况下，当前子区域中所有格子的和为 0。
那么显然我们可以维护一个二维的前缀和数组，在 O(1) 的时间复杂度下就可以判断每次遍历到的格子是否能贴邮票。
而因为贴邮票的操作，可以概括为将当前子区域的所有格子的值都置为 1，很自然的就能想到用一个二维的差分数组来维护贴邮票后的状态。
最后只要对该差分数组再求一次二维前缀和，只要当前格子的和为 0，就意味着存在没有覆盖完全的情况，直接返回 false 即可。
需要注意的是二维数组的下标关系，具体参考如下。
s[i + 1][j + 1] 表示第 i 行第 j 列左上部分所有元素之和，其中 i, j 下标从 0 开始。
则 s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + nums[i][j]。
以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵和 sub = s[x2 + 1][y2 + 1] - s[x2 + 1][y1] - s[x1][y2 + 1] + s[x1][y1]。
class Solution:
def possibleToStamp(
self, grid: List[List[int]], stampHeight: int, stampWidth: int
) -> bool:
m, n = len(grid), len(grid[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(grid):
for j, v in enumerate(row):
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + v
d = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(grid):
for j, v in enumerate(row):
if v == 0:
x, y = i + stampHeight, j + stampWidth
if x <= m and y <= n and s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0:
d[i][j] += 1
d[i][y] -= 1
d[x][j] -= 1
d[x][y] += 1
cnt = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(grid):
for j, v in enumerate(row):
cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j]
if v == 0 and cnt[i + 1][j + 1] == 0:
return False
return Trueclass Solution {
public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
int m = grid.length, n = grid[0].length;
int[][] s = new int[m + 1][n + 1];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
}
}
int[][] d = new int[m + 1][n + 1];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
int x = i + stampHeight, y = j + stampWidth;
if (x <= m && y <= n && s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0) {
d[i][j]++;
d[i][y]--;
d[x][j]--;
d[x][y]++;
}
}
}
}
int[][] cnt = new int[m + 1][n + 1];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) {
return false;
}
}
}
return true;
}
}class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> s(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
}
}
vector<vector<int>> d(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) continue;
int x = i + stampHeight, y = j + stampWidth;
if (x <= m && y <= n && s[x][y] - s[i][y] - s[x][j] + s[i][j] == 0) {
d[i][j]++;
d[x][j]--;
d[i][y]--;
d[x][y]++;
}
}
}
vector<vector<int>> cnt(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) return false;
}
}
return true;
}
};impl Solution {
pub fn possible_to_stamp(grid: Vec<Vec<i32>>, stamp_height: i32, stamp_width: i32) -> bool {
let n: usize = grid.len();
let m: usize = grid[0].len();
let mut prefix_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Initialize the prefix vector
for i in 0..n {
for j in 0..m {
prefix_vec[i + 1][j + 1] = prefix_vec[i][j + 1] + prefix_vec[i + 1][j] - prefix_vec[i][j] + grid[i][j];
}
}
let mut diff_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Construct the difference vector based on prefix sum vector
for i in 0..n {
for j in 0..m {
// If the value of the cell is one, just bypass this
if grid[i][j] == 1 {
continue;
}
// Otherwise, try stick the stamp
let x: usize = i + stamp_height as usize;
let y: usize = j + stamp_width as usize;
// Check the bound
if x <= n && y <= m {
// If the region can be sticked (All cells are empty, which means the sum will be zero)
if prefix_vec[x][y] - prefix_vec[x][j] - prefix_vec[i][y] + prefix_vec[i][j] == 0 {
// Update the difference vector
diff_vec[i][j] += 1;
diff_vec[x][y] += 1;
diff_vec[x][j] -= 1;
diff_vec[i][y] -= 1;
}
}
}
}
let mut check_vec: Vec<Vec<i32>> = vec![vec![0; m + 1]; n + 1];
// Check the prefix sum of difference vector, to determine if there is any empty cell left
for i in 0..n {
for j in 0..m {
// If the value of the cell is one, just bypass this
if grid[i][j] == 1 {
continue;
}
// Otherwise, check if the region is empty, by calculating the prefix sum of difference vector
check_vec[i + 1][j + 1] = check_vec[i][j + 1] + check_vec[i + 1][j] - check_vec[i][j] + diff_vec[i][j];
if check_vec[i + 1][j + 1] == 0 {
return false;
}
}
}
true
}
}func possibleToStamp(grid [][]int, stampHeight int, stampWidth int) bool {
m, n := len(grid), len(grid[0])
s := make([][]int, m+1)
d := make([][]int, m+1)
cnt := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
d[i] = make([]int, n+1)
cnt[i] = make([]int, n+1)
}
for i, row := range grid {
for j, v := range row {
s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + v
}
}
for i, row := range grid {
for j, v := range row {
if v == 0 {
x, y := i+stampHeight, j+stampWidth
if x <= m && y <= n && s[x][y]-s[i][y]-s[x][j]+s[i][j] == 0 {
d[i][j]++
d[i][y]--
d[x][j]--
d[x][y]++
}
}
}
}
for i, row := range grid {
for j, v := range row {
cnt[i+1][j+1] = cnt[i+1][j] + cnt[i][j+1] - cnt[i][j] + d[i][j]
if v == 0 && cnt[i+1][j+1] == 0 {
return false
}
}
}
return true
}/**
* @param {number[][]} grid
* @param {number} stampHeight
* @param {number} stampWidth
* @return {boolean}
*/
var possibleToStamp = function (grid, stampHeight, stampWidth) {
const m = grid.length;
const n = grid[0].length;
let s = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
let d = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
let cnt = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
let [x, y] = [i + stampHeight, j + stampWidth];
if (
x <= m &&
y <= n &&
s[x][y] - s[i][y] - s[x][j] + s[i][j] == 0
) {
d[i][j]++;
d[i][y]--;
d[x][j]--;
d[x][y]++;
}
}
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
cnt[i + 1][j + 1] =
cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) {
return false;
}
}
}
return true;
};