Załóż tablicę logiczną taką jak:

1111
1111
1110
1111
1001

Teraz musisz znaleźć sposób na ułożenie najmniejszych prostokątów o dowolnym rozmiarze, aby osiągnąć ten kształt. Na przykład znajdziesz to:

+-++
| |+
| |
+-++
+  +

Gdzie + to róg prostokąta i |, - granice prostokąta.

To, co myślałem o zrobieniu, to rozpoczęcie od największego możliwego prostokąta, sprawdzenie, czy w tablicy znajduje się jakiekolwiek miejsce, w którym można go umieścić, gdzie każdy element tablicy objęty prostokątem jest prawdziwy. Jeśli takie miejsce istnieje, prostokąt zostanie dodany do listy. Następnie sprawdzamy w lewym polu tablicy, czy jest inne miejsce do umieszczenia prostokąta, a następnie zmniejszamy rozmiar prostokąta i powtarzamy proces z pozostałą przestrzenią, aż rozmiar będzie równy 0.

Powinno to dać dobre wyniki, ponieważ zawsze zaczynamy od dużych prostokątów, które możemy - oczywiście - użyć mniej, co z kolei oznacza, że ​​używamy małych ilości prostokątów.

Jednak jest to tylko koncepcja, o której myślałem, a której jeszcze nie wprowadziłem w życie. Wydaje się to dość nieefektywne, więc zastanawiałem się, czy istnieją jakieś znane szybkie algorytmy do osiągnięcia tego celu?