I have an N by N grid of cells, and certain blocks are marked:
<code>+--+---+---+---+
| | | | |
| | x | x | |
| | x | x | |
| | | | |
| | | | x |
+--+---+---+---+
</code>
<code>+--+---+---+---+
| | | | |
| | x | x | |
| | x | x | |
| | | | |
| | | | x |
+--+---+---+---+
</code>
+--+---+---+---+
| | | | |
| | x | x | |
| | x | x | |
| | | | |
| | | | x |
+--+---+---+---+
I would like to find a set of non-overlapping rectangles that covers all marks but not the unmarked cells. In the example that would be 2, one with topleft corner at (2,2) of size 2×2 and on of size 1×1 at (5,4)
Does anyone know an algorithm or the formal name of this problem?
7