Il più piccolo numero di rettangoli che coprono parti segnate della griglia

3

Ho una griglia N di celle N e alcuni blocchi sono contrassegnati:

+--+---+---+---+
|  |   |   |   |
|  | x | x |   |
|  | x | x |   |
|  |   |   |   |
|  |   |   | x |
+--+---+---+---+

Mi piacerebbe trovare un insieme di rettangoli non sovrapposti che copra tutti i segni ma non le celle non marcate. Nell'esempio che sarebbe 2, uno con angolo a topleft a (2,2) di dimensione 2x2 e su dimensione 1x1 a (5,4)

Qualcuno conosce un algoritmo o il nome formale di questo problema?

    
posta dtech 30.04.2015 - 13:32
fonte

0 risposte

Leggi altre domande sui tag