diff options
Diffstat (limited to 'stamping_the_grid.c')
-rw-r--r-- | stamping_the_grid.c | 89 |
1 files changed, 89 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); +} |