2132.用邮票贴满网格图

链接：2132.用邮票贴满网格图
难度：Hard
标签：贪心、数组、矩阵、前缀和
简介：如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

题解 1 - python

• 编辑时间：2023-12-14
• 执行用时：1440ms
• 内存消耗：57.3MB
• 编程语言：python
• 解法介绍：前缀和统计区间内有无禁区，差分统计空白区是否都存在邮票。

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n, m = len(grid), len(grid[0])
        sums = [[0] * (m + 2) for _ in range(n + 2)]
        arr  = [[0] * (m + 2) for _ in range(n + 2)]
        for i in range(n):
            for j in range(m):
                sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + grid[i][j]
        for i in range(n):
            for j in range(m):
                endi = i + stampHeight - 1
                endj = j + stampWidth  - 1
                if grid[i][j] == 0 and endi < n and endj < m and sums[endi + 1][endj + 1] - sums[endi + 1][j] - sums[i][endj + 1] + sums[i][j] == 0:
                    arr[i + 1][j + 1]        += 1
                    arr[i + 1][endj + 2]     -= 1
                    arr[endi + 2][j + 1]     -= 1
                    arr[endi + 2][endj + 2]  += 1
        
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                arr[i][j] += arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1]
                if grid[i - 1][j - 1] == 0 and arr[i][j] == 0:
                    return False
        return True