Ma trận khu vực tối thiểu bao gồm

Question

Xem xét ma trận nhị phân n-by-n, tôi muốn tìm diện tích tối thiểu của hai hình chữ nhật có thể bao phủ tất cả các hình chữ nhật (1s). Tức là, tổng diện tích của hình chữ nhật phải nhỏ nhất. Các hình chữ nhật có thể chồng lên nhau.

Ví dụ:

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 

Diện tích tối thiểu là: 3 * 9 + 9 * 3 = 54

Tôi muốn biết nếu có một giải pháp tốt hơn so với O(n^4).

Answer 1

Trước tiên, bạn có thể giải quyết vấn đề cho một hình chữ nhật bằng cách tìm các số 1 ở trên cùng, dưới cùng, tận cùng bên phải và tận cùng bên trái trong ma trận. Sau đó, bạn biết rằng bạn có thể cải thiện kết quả của bạn bằng cách sử dụng một hình chữ nhật thứ hai nếu và chỉ khi bạn có thể cắt ra khối đối xứng của tất cả 0s.