LC 2132. 用邮票贴满网格图

https://leetcode-cn.com/problems/stamping-the-grid/

这题有两个点,一个点是如果在(r,c)上粘贴邮票是否可行,这个通过预处理数组可以得到。

另外一个点则是,位置(r,c)是否可以被某个邮票所覆盖。

一个可行的思路是,保留最近 `stampHeight` 行所有可以粘贴邮票的 columns.

如果有某个column满足 `c-stampWidth+1<= column <= c` 的话,那么就认为这个位置是可以被之前粘贴的邮票覆盖上的。

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n, m = len(grid), len(grid[0])

        acc = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n):
            tt = 0
            for j in range(m):
                tt += grid[i][j]
                acc[i + 1][j + 1] = tt
            for j in range(m):
                acc[i + 1][j + 1] += acc[i][j + 1]

        # print(acc)

        def values(r, c, r2, c2):
            a = acc[r2 + 1][c2 + 1] - acc[r2 + 1][c]
            b = acc[r][c2 + 1] - acc[r][c]
            return a - b

        def valid(r, c):
            r2, c2 = r + stampHeight - 1, c + stampWidth - 1
            if 0 <= r2 < n and 0 <= c2 < m:
                return values(r, c, r2, c2) == 0
            return False

        from sortedcontainers import SortedList
        sl = SortedList()
        for r in range(n):
            if r >= stampHeight:
                r2 = r - stampHeight
                for c in range(m):
                    if valid(r2, c):
                        sl.remove(c)
            for c in range(m):
                if valid(r, c):
                    sl.add(c)

            # print(sl)
            # check it can be covered.
            for c in range(m):
                if grid[r][c] == 1: continue
                c2 = max(0, c - stampWidth + 1)
                pos = sl.bisect_left(c2)
                if pos < len(sl) and sl[pos] <= c:
                    pass
                else:
                    return False

        return True