Menyesuaikan jumlah minimum persegi panjang lebar / tinggi 1 ke dalam kisi 2D

Pertimbangkan masalah di mana Anda diberi kisi 2D (misalnya papan catur) di mana kotak-kotak tertentu ditempati dan Anda perlu menempatkan jumlah minimum persegi panjang non-tumpang tindih dari berbagai ukuran wxh di mana w = 1 atau h = 1 (yaitu "persegi" segmen ") sedemikian rupa sehingga semua kotak kosong dihuni dan masing-masing kotak hanya mencakup kotak kosong.

Misalnya, untuk kisi

..###
.....
..###
.#...

solusinya adalah 4, karena Anda dapat menutupi semua kotak kosong (dilambangkan dengan '.') dengan 4 persegi panjang seperti berikut:

12###
12333
12###
1#444

Saya mencoba untuk datang dengan algoritma polinomial atau membuktikan bahwa masalah ini NP-keras, tetapi tidak berhasil. Adakah yang bisa membantu saya untuk membuktikan / menyangkal bahwa ini masalah dalam P, atau mengarahkan saya ke beberapa pekerjaan / masalah terkait?

$P$$1\times a$$b\times 1$

$G$$P$$P$$G$$v$$G$$s$$v$$s$

$R=S-I$$R$$S$$P$$I$$I$$S$$R$$I$$P$$G$$G$adalah grafik bipartit (segmen horisontal hanya berbatasan dengan segmen vertikal dan sebaliknya) sehingga set independen maksimumnya dapat ditemukan dalam waktu polinomial (lihat teorema König di Wikipedia).