How can I find the minimum number of open rectangles in a grid?

Find minimum number of rectangles of length 2 in a grid of binary values

• Given a grid, I need to "cover" the true values with rectangles. The rectangles can only be horizontal or vertical and they can cover two cells at max. For example, in this case: 1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 the minimum number of ractangles is 4: 1 from [0][0] to [1][0], 2 from [0][1] to [0][2], 3 with only [1][4] (since there aren't any adjacent 1s in the up, down, left and right directions) and the last one with only [2][3] in it. I suppose, the problem comes when the grid has many consecutive 1s that split in many directions. For example 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 or 1 1 1 1 0 1 1 1 1 I cannot think of a pretty efficient algorithm to solve this problem, a greedy approach seems to be ineffective. Any help would be really much appreciated, thanks. EDIT: The greedy algorithm I've tried: scan the matrix 1 row at a time, if there's a 1 in the current position, then check if there's another 1 in the next row position [rowIndex][columnIndex + 1] and "cover" both with one rectangle. If not, check the cell below the current position [rowIndex + 1][columnIndex] and do as before. If there aren't any 1s in these positions, cover only the current cell. As you can see, this algorithm doesn't work in the first case. Perhaps the algorithm must know all the consecutive 1s to compute the minimum number of rectangles. Because of this, I'm wondering if some graph stuff comes in, but I can't still think of an optimal solution.

• Answer:

  I would simply go through the matrix and as soon I see a 1 I try to create a new rectangle with an adjacent 1 which can be on the same line or row and has no other adjacent 1 otherwise the rectangle will cover only the current cell and then you scan the matrix until you find a new uncovered 1 or you have scanned the enteir matrix, in this way you can cover all the 1 with the minumum number of rectangle (if I'm not wrong). for i=0 to N for j=0 to M if (1==matrix[i][j] AND notCovered(i,j)){ k,l=adjacent(i,j)//return an adjacent 1 that cannot be covered, if all the adjacent 1 can be covered return the one on the same row if (k AND l == VOID ) cover (i,j) else cover (i,j)(k,l) } Of course you can do some improvement on this algorithm, I hope this will help you