Minimal alan matrisi kaplaması

Question

Bir n-by-n ikili matrisini göz önünde bulundurarak, hepsini (1s) kapsayacak şekilde en az iki dikdörtgenin alanını bulmak istiyorum. Yani, dikdörtgenlerin alanlarının toplamı minimal olmalıdır. Dikdörtgenler üst üste binebilir.

Örnek:

0 0 0 1 1 1 0 0 0 
0 0 0 1 1 1 0 0 0 
0 0 0 1 1 1 0 0 0 
1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
0 0 0 1 1 1 0 0 0 
0 0 0 1 1 1 0 0 0 
0 0 0 1 1 1 0 0 0 

asgari alandır: 3 * 9 + 9 * 3 = 54

Ben O(n^4) daha çözüm daha iyi olup olmadığını bilmek ilgileniyorum.

Answer 1

Matristeki en yukarı, en aşağı, en sağa ve en soldaki 1leri bularak sorunu bir dikdörtgen için çözebilirsiniz. Daha sonra, eğer tüm 0'ların simetrik parçalarını kesebilirseniz ikinci bir dikdörtgen kullanarak sonucunuzu geliştirebileceğinizi biliyorsunuzdur.