覆盖网格中占用的单元格所需的最小矩形？ [英] Minimum rectangles required to cover occupied cells in a grid?

问题描述

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

Given an RxC grid out of which certain cells are occupied, what is the minimum number of rectangles needed to cover the occupied cells?

• 每个矩形都是Rx1或1xC


• 矩形可以重叠


• 被占用的单元格可以覆盖一次以上

示例：（x-占用）

x----

- -x--

-x-xx

x-x--

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

所需的最小矩形为3。（封面第1列，第2列，第3列）

The minimum rectangles needed is 3. (Cover column 1, column 2, row 3)

有人能指出我正确的方向吗？这似乎很容易，但是我无法找到一个可靠的解决方案！

Can anyone point me in the right direction? This seems easy enough but I am not able to arrive at a robust solution!

谢谢。

推荐答案

考虑一个具有两部分的图形，第一部分的顶点与行有关，第二部分与列对顶点。部分 1 中的顶点 i 连接到顶点 j 来自 2 部分，如果 a [i] [j] =='x'。然后，问题就减少了，找到了最小顶点覆盖率，例如图的每条边具有至少一个端点的最小顶点集。由于该图是二部图，因此可以在多项式时间内完成，请参见此帖子。

Consider a graph with two parts, the vertices in the first part respects to rows and vertices from the second respects to columns. The vertex i from part 1 is connected to vertex j from part 2 iff a[i][j] == 'x'. Then the problem is reduced to finding a minimum vertex cover, e.g. minimum set of vertices that each edge of the graph has at least one endpoint from this set. As the graph is bipartite it can be done in polynomial time, see this post.

这篇关于覆盖网格中占用的单元格所需的最小矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！