2

Suppose I have a grid containing 1's and 0's... How can I find the shortest list of rectangles (really, boundaries) that, together, cover all of the 1's and don't cover any 0's?

Currently, I'm repeatedly finding the largest rectangle in the grid, storing it's dimensions, and setting all of the cells in the area to 0, until they are all set to 0.

My two issues with this are: it seems very efficient, and I can't seem to prove that it actually covers the area in the fewest rectangles but I can't find any scenarios to disprove it either.

Update: I found a grid that disproves the method I described...

0000000
0000010
0111110
0000010
0000000

The horizontal string of 1's is the largest existing rectangle, but once removed, it splits the vertical string of 1's into two small rectangles... Clearly, this could be solved in just 2 rectangles.

DanRedux
  • 9,119
  • 6
  • 23
  • 41

1 Answers1

0

A generic depth first search of the solution space may not be the most efficient, but will find the answer. You can even have it output every solution (for example the grid you show has two solutions where every '1' is covered using just two triangles.) This should be easy to implement and then you can use it as a baseline to compare with other methods, both to test them for correctness and to compare times.

A slight modification of your current method would solve that example grid: Find the 'largest' grid in terms of how many currently uncovered squares it covers, and instead of changing squares to '0' have a separate state that means '1' but already covered. This way later rectangles can span these squares but already covered squares don't count toward making rectangles 'larger'. (Of course this only works if you're allowed to have overlapping rectangles.)

bames53
  • 86,085
  • 15
  • 179
  • 244