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:
- 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 each other.
- Stamps are not allowed to be rotated.
- 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++) { 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++) { if(!grid[i][j]) st[j] += 1; else st[j] = 0; } queue<int> q; for(int j = 0; j < w - 1; j++) { if(st[j] < h) q.push(j); } for(int l = 0, r = w - 1; r < m; l++,r++) { 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++) { 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++) { sum += row[j]; if(!sum and !grid[i][j]) { return false; } } } return true; } };
|