We can check if every empty cell is a part of a consecutive row of empty cells that has a width of at least stampWidth as well as a consecutive column of empty cells that has a height of at least stampHeight.

We can prove that this condition is sufficient and necessary to fit the stamps while following the given restrictions and requirements.

For each row, find every consecutive row of empty cells, and mark all the cells where the consecutive row is at least stampWidth wide. Do the same for the columns with stampHeight. Then, you can check if every cell is marked twice.