diff options
Diffstat (limited to 'stamping_the_grid.py')
-rw-r--r-- | stamping_the_grid.py | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/stamping_the_grid.py b/stamping_the_grid.py new file mode 100644 index 0000000..27abb3a --- /dev/null +++ b/stamping_the_grid.py @@ -0,0 +1,66 @@ +# 2132. Stamping the Grid +from itertools import product + +""" +you are given an 'm x n' binary matrix 'grid' where each cell is either 0 or +1 (empty or occupied, respectively). you are then given stamps of size +'stampHeight x stampWidth'. we want to fit the stamps such that they follow +the given restrictions and requirements: cover all the empty cells, do not +cover any of the occupied cells, we can put as many stamps as we want, stamps +can overlap with eachother, stamps are not allowed to be rotated, stampsmust +stay completely in the grid. return 'true' if it is possible to fit the +stamps while following the given restrictions, otherwise return 'false'. +""" + + +class Solution(object): + def possibleToStamp(self, grid, stampHeight, stampWidth): + """ + :type grid: List[List[int]] + :type stampHeight: int + :type stampWidth: int + :rtype: bool + """ + + def acc_2d(grid): + dp = [[0] * (n + 1) for _ in range(m + 1)] + for c, r in product(range(n), range(m)): + dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] - dp[r][c] + grid[r][c] + return dp + + def sumRegion(r1, c1, r2, c2): + return dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1] + + m, n = len(grid), len(grid[0]) + dp = acc_2d(grid) + diff = [[0] * (n + 1) for _ in range(m + 1)] + for c in range(n - stampWidth + 1): + for r in range(m - stampHeight + 1): + if sumRegion(r, c, r + stampHeight - 1, c + stampWidth - 1) == 0: + diff[r][c] += 1 + diff[r][c + stampWidth] -= 1 + diff[r + stampHeight][c] -= 1 + diff[r + stampHeight][c + stampWidth] += 1 + dp2 = acc_2d(diff) + for c, r in product(range(n), range(m)): + if dp2[r + 1][c + 1] == 0 and grid[r][c] != 1: + return False + return True + + +if __name__ == "__main__": + obj = Solution() + print( + obj.possibleToStamp( + 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, + ) + ) + print( + obj.possibleToStamp( + grid=[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], + stampHeight=2, + stampWidth=2, + ) + ) |