2132. 用邮票贴满网格图（困难，二维前缀和，二维差分）

本文主要是介绍2132. 用邮票贴满网格图（困难，二维前缀和，二维差分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

通过二维前缀和，我们可以快速判断以 i，j 为右下顶点是否能贴邮票，其递推关系为
即 sum(i, j) 为0就表示以 i，j 为右下顶点能贴邮票，也就是以 i - stampHeight + 1，j - stampWidth + 1的顶点为左上角能够贴邮票
然后判断是否贴满，设diff数组，其递归关系为（在第四步之后，遍历矩阵，用sum来贴邮票的同时，根据下式来判断每个点是否被贴上，因为我们只贴左上角，所以这么同时做是可行的）：
由下图可以看到，更新sum数组的同时更新diff，当在 i， j 位置贴邮票时，接下来的邮票覆盖范围内应当diff全为大于0的数表示被邮票覆盖了，而抽超出邮票范围的绿色区域就该-1来保证蓝色邮票覆盖范围的有限性，同样的黄色区域的加1是为了平衡两个-1，使得总和为0

class Solution:def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:m, n = len(grid), len(grid[0])psum = [[0] * (n + 2) for _ in range(m + 2)]diff = [[0] * (n + 2) for _ in range(m + 2)]for i in range(1, m + 1):for j in range(1, n + 1):psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + grid[i - 1][j - 1]for i in range(1, m + 2 - stampHeight):for j in range(1, n + 2 - stampWidth):x = i + stampHeight - 1y = j + stampWidth - 1if psum[x][y] - psum[x][j - 1] - psum[i - 1][y] + psum[i - 1][j - 1] == 0:diff[i][j] += 1diff[i][y + 1] -= 1diff[x + 1][j] -= 1diff[x + 1][y + 1] += 1for i in range(1, m + 1):for j in range(1, n + 1):diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]if diff[i][j] == 0 and grid[i - 1][j - 1] == 0:return Falsereturn True