Considere um problema no qual você recebe uma grade 2D (por exemplo, um tabuleiro de xadrez) em que certos quadrados estão ocupados e você precisa colocar o número mínimo de retângulos sem sobreposição de qualquer tamanho wxh em que w = 1 ou h = 1 (ou seja, "quadrado" segmentos ") de forma que todos os quadrados desocupados sejam cobertos e cada retângulo cubra apenas quadrados desocupados.
Por exemplo, para a grade
..###
.....
..###
.#...
a solução seria 4, já que você pode cobrir todos os quadrados desocupados (indicados por '.') com 4 retângulos da seguinte maneira:
12###
12333
12###
1#444
Tentei criar um algoritmo polinomial ou provar que esse problema é difícil para o NP, mas sem sucesso. Alguém pode me ajudar a provar / refutar que este é um problema em P ou apontar-me para alguns trabalhos / problemas relacionados?
Respostas:
fonte