最小面积的矩阵覆盖

本文介绍了最小面积的矩阵覆盖的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

正由-N二元矩阵考虑，我想找到两个矩形的最小面积，将覆盖所有的人（1秒）。也就是，的矩形的面积的总和必须是最小的。 该矩形可以重叠。

Considering an n-by-n binary matrix, I would like to find the minimal area of two rectangles that would cover all the ones (1s). That is, the sum of the areas of the rectangles must be minimal. The rectangles can overlap.

例如：

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

的最小面积是： 3 * 9 + 9 * 3 = 54

我很想知道，如果有一个解决方案优于为O（n ^ 4）。

I'm interested to know if there is a solution better than O(n^4).

推荐答案

您可以先解决这个问题一个矩形通过查找至上，最下面，最右边，最左侧1秒的矩阵。然后，你知道，你可以通过使用第二个矩形当且仅当你能切出全0的对称块提高你的结果。

You can first solve the problem for one rectangle by finding the upmost, downmost, rightmost, and leftmost 1s in the matrix. Then you know that you can improve your result by using a second rectangle if and only if you can cut out symmetrical chunks of all 0s.