[LeetCode] Stamping the Grid

2132. Stamping the Grid

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).

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:

  1. Cover all the empty cells.
  2. Do not cover any of the occupied cells.
  3. We can put as many stamps as we want.
  4. Stamps can overlap with each other.
  5. Stamps are not allowed to be rotated.
  6. Stamps must stay completely inside the grid.

Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
bool judge(vector<vector<int>>& grid) {
int sum = 0;
for(auto& r : grid)
sum += accumulate(begin(r),end(r),0);
return sum == grid.size() * grid[0].size();
}
public:
bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
int n = grid.size(), m = grid[0].size();
if(h > n or w > m) return judge(grid);
vector<int> st(m, 0);
vector<vector<bool>> mark(n, vector<bool>(m));

for(int i = 0; i < h - 1; i++) { //pre calculate with dp technique
for(int j = 0; j < m; j++) {
if(!grid[i][j]) st[j] += 1;
else st[j] = 0;
}
}

for(int i = h - 1; i < n; i++) {
for(int j = 0; j < m; j++) {// dp technique
if(!grid[i][j]) st[j] += 1;
else st[j] = 0;
}
queue<int> q;
for(int j = 0; j < w - 1; j++) { //sliding window technique
if(st[j] < h) q.push(j);
}
for(int l = 0, r = w - 1; r < m; l++,r++) { //marking top left of stamp
while(!q.empty() and q.front() < l) q.pop();
if(st[r] < h) q.push(r);
if(q.empty()) mark[i-h+1][l] = true;
}
}

vector<int> row(m + 1);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) { //diff array technique
if(mark[i][j]) {
row[j]++;
row[j + w]--;
}
if(i >= h and mark[i-h][j]) {
row[j]--;
row[j + w]++;
}
}
int sum = 0;
for(int j = 0; j < m; j++) { //prefix sum technique
sum += row[j];
if(!sum and !grid[i][j]) {
return false;
}
}
}

return true;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/04/21/PS/LeetCode/stamping-the-grid/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.