#2132
Stamping the Grid
master · 1855 · lc hard +32 · verified · 35% accepted · 418 likes · top 13%
Description
You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied).
You also have stamps of fixed size stampHeight x stampWidth. Place stamps on the grid following these constraints:
- All empty cells must be covered by at least one stamp.
- No stamp may cover any occupied cell.
- Stamps may be placed in unlimited quantity.
- Stamps may overlap one another.
- Stamps cannot be rotated.
- Stamps must remain entirely within the grid boundaries.
Return true if it is possible to cover all empty cells under these constraints, otherwise return false.
Example 1:
Input: 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
Output: true
Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.
Example 2:
Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2
Output: false
Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
Code
1
2
3