Given that the RxC grid from which certain cells are occupied, what is the minimum number of rectangles needed to cover the occupied cells?
- Each rectangle is either Rx1 or 1xC
- Rectangles may overlap
- Occupied cells can be closed more than once
Example: (x - busy)
x - - - -
- - x - -
- x - xx
x - x - -
The required minimum rectangles are 3. (Shell 1, Column 2, Line 3)
Can someone point me in the right direction? It seems simple enough, but I can’t find a reliable solution!
Thanks.
source
share