2132. 用邮票贴满网格图 (困难,二维前缀和,二维差分)

2023-12-14 16:12:52

在这里插入图片描述

  1. 通过二维前缀和,我们可以快速判断以 i,j 为右下顶点是否能贴邮票,其递推关系为在这里插入图片描述
  2. 即 sum(i, j) 为0就表示以 i,j 为右下顶点能贴邮票,也就是以 i - stampHeight + 1,j - stampWidth + 1的顶点为左上角能够贴邮票
  3. 然后判断是否贴满,设diff数组,其递归关系为(在第四步之后,遍历矩阵,用sum来贴邮票的同时,根据下式来判断每个点是否被贴上,因为我们只贴左上角,所以这么同时做是可行的):在这里插入图片描述
  4. 由下图可以看到,更新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 - 1
                y = j + stampWidth - 1
                if psum[x][y] - psum[x][j - 1] - psum[i - 1][y] + psum[i - 1][j - 1] == 0:
                    diff[i][j] += 1
                    diff[i][y + 1] -= 1
                    diff[x + 1][j] -= 1
                    diff[x + 1][y + 1] += 1

        for 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 False
        return True

文章来源:https://blog.csdn.net/qq_46636391/article/details/134994211
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。