Fit The Stamp :
Difficulty Level : Hard
Submissions : 68
Asked In :
Marks :100
: 1 | : 0
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.
The first line of input contains two integers N and M the size of the matrix($$$ 1 \le N, M \le 10^5$$$)
The next lines contain the input for the matrix
The next line contains StampHeight and StampWidth. ($$$1 \le StampHeight ,StampWidth \le 10^5$$$)
Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.
5 4 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 4 3
1
4 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 2 2
0
