algorithm - 如何计算覆盖网格中占用的单元格所需的最小矩形数？

Question

给定一个R × C 网格，其中某些单元被占用，覆盖被占用单元所需的最小矩形数是多少？

• 每个矩形要么是 R ×1 要么是 1× C。
• 矩形可以重叠。
• 占用的单元格可以覆盖多个矩形。

例子：

x - - - -
- - x - -
- x - x x
x - x - -

在这里x 分别 -标记被占用和未被占用的单元格。

在这种情况下，最少需要 3 个矩形。（覆盖第 1 列、第 2 列和第 3 行。）

谁能指出我正确的方向？这似乎很容易，但我无法找到一个强大的解决方案！

Answer 1

考虑一个由两组顶点组成的二分图，第一组中的顶点对应于行，第二组中的顶点对应于网格的列。来自第一组的顶点 i连接到 来自第二组 iff的顶点ja[i][j] == 'x'。

然后问题被简化为找到该图的最小顶点覆盖，即最小的顶点集，使得图的每条边至少有一个端点存在于该集中。由于图是二分图，因此可以在多项式时间内计算出最小顶点覆盖；看到这个帖子。