diff options
author | Jack Sangdahl <[email protected]> | 2025-01-21 12:38:29 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-21 12:38:29 -0700 |
commit | 9a3155d502b44f90ee671b23c8b76dec0079a98f (patch) | |
tree | 384ae50aeef8c41dd6505f1321f8d6617aa85d77 | |
parent | f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840 (diff) | |
download | leetcode-9a3155d502b44f90ee671b23c8b76dec0079a98f.tar.gz leetcode-9a3155d502b44f90ee671b23c8b76dec0079a98f.zip |
2132. stamping the grid
-rw-r--r-- | stamping_the_grid.c | 89 | ||||
-rw-r--r-- | stamping_the_grid.py | 66 |
2 files changed, 155 insertions, 0 deletions
diff --git a/stamping_the_grid.c b/stamping_the_grid.c new file mode 100644 index 0000000..e874acc --- /dev/null +++ b/stamping_the_grid.c @@ -0,0 +1,89 @@ +// 2132. Stamping the Grid +#include "leetcode.h" + +/* + * 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'. + */ + +bool possibleToStamp(int **grid, int gridSize, int *gridColSize, + int stampHeight, int stampWidth) { + int n = gridSize, m = m; + int occupied[n][m]; + bool stamps[n][m]; + memset(occupied, 0, sizeof(occupied)); + for (int i = 0; i < n; i++) + for (int j = 0; j < m; j++) { + occupied[i][j] = grid[i][j]; + if (i) + occupied[i][j] += occupied[i - 1][j]; + if (j) + occupied[i][j] += occupied[i][j - 1]; + if (i && j) + occupied[i][j] -= occupied[i - 1][j - 1]; + } + memset(stamps, false, sizeof(stamps)); + for (int i = 0; i < n; i++) + for (int j = 0; j < m; j++) + if (!grid[i][j]) { + const int x = i + stampHeight - 1, y = j + stampWidth - 1; + if (x < n && y < m) { + int ones = occupied[x][y]; + if (j) + ones -= occupied[x][j - 1]; + if (i) + ones -= occupied[i - 1][y]; + if (i && j) + ones += occupied[i - 1][j - 1]; + if (!ones) + stamps[i][j] = true; + } + } + memset(occupied, 0, sizeof(occupied)); + for (int i = 0; i < n; i++) + for (int j = 0; j < m; j++) { + occupied[i][j] = stamps[i][j] ? 1 : 0; + if (i) + occupied[i][j] += occupied[i - 1][j]; + if (j) + occupied[i][j] += occupied[i][j - 1]; + if (i && j) + occupied[i][j] -= occupied[i - 1][j - 1]; + } + for (int i = 0; i < n; i++) + for (int j = 0; j < m; j++) + if (!grid[i][j]) { + const int x = i - stampHeight, y = j - stampWidth; + int stamp_cnt = occupied[i][j]; + if (x >= 0) + stamp_cnt -= occupied[x][j]; + if (y >= 0) + stamp_cnt -= occupied[i][y]; + if (x >= 0 && y >= 0) + stamp_cnt += occupied[x][y]; + if (!stamp_cnt) + return false; + } + return true; +} + +int main() { + int g1i[6][4] = { + {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}}; + int g2i[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}; + struct two_d_arr g1, g2; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + printf("%d\n", + possibleToStamp(g1.arr, g1.row_size, g1.col_size, 4, 3)); // expect: 1 + printf("%d\n", + possibleToStamp(g2.arr, g2.row_size, g2.col_size, 2, 2)); // expect: 0 + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} 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, + ) + ) |