title: Find minimum number of rectangles of length 2 in a grid of binary values
body: <p>Given a grid, I need to "cover" the <strong>true</strong> values with rectangles. The rectangles can only be horizontal or vertical and they can cover two cells at max.  </p>
  
  <p>For example, in this case:</p>
  
  <pre>
  1 1 1 0 0  
  1 0 0 0 1
  0 0 0 1 0
  </pre>
  
  <p>the minimum number of ractangles is 4: 1 from <strong>[0][0]</strong> to <strong>[1][0]</strong>, 2 from <strong>[0][1]</strong> to <strong>[0][2]</strong>, 3 with only <strong>[1][4]</strong> (since there aren't any adjacent 1s in the up, down, left and right directions) and the last one with only <strong>[2][3]</strong> in it.</p>
  
  <p>I suppose, the problem comes when the grid has many consecutive 1s that split in many directions. For example</p>
  
  <pre>
  1 1 1 1 1
  1 0 0 0 0
  1 0 0 1 0
  1 1 1 1 0
  </pre>
  
  <p>or</p>
  
  <pre>
  1 1 1
  1 0 1
  1 1 1
  </pre>
  
  <p>I cannot think of a pretty efficient algorithm to solve this problem, a greedy approach seems to be ineffective. </p>
  
  <p>Any help would be really much appreciated, thanks.</p>
  
  <p>EDIT:</p>
  
  <p>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 <strong>[rowIndex][columnIndex + 1]</strong> and "cover" both with one rectangle. If not, check the cell below the current position <strong>[rowIndex + 1][columnIndex]</strong> 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. <em>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.</em>     </p>