如何计算覆盖网格中占用的单元格所需的最小矩形数? [英] How to compute the minimum number of rectangles required to cover occupied cells in a grid?

问题描述

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

• 每个矩形是 R ×1或1× C .
• 矩形可以重叠.
• 被占领的牢房可以覆盖一个以上的矩形.

示例:

  x----- - X - --x-xxx-x-- 

分别在 x 和-标记占用和未占用的单元格.

在这种情况下，最少需要矩形的数目为3.(覆盖第1列，第2列和第3行.)

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

解决方案

考虑一个二部图，该二部图由两组顶点组成，其中第一组顶点对应于行，第二组顶点对应于行.网格的列.第一组顶点 i 与第二组顶点 j 连接iff a [i] [j] =='x'.

然后，问题就减少了，找到了该图的最小顶点覆盖，即，最小的一组顶点，以使图形的每个边缘在此集合中至少存在一个端点.由于该图是二部图，因此可以在多项式时间内计算最小顶点覆盖度；参见这篇文章.>

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

• Each rectangle is either R×1 or 1×C.
• Rectangles can overlap.
• Occupied cells can be covered more than one rectangle.

Example:

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

Here x and - mark occupied and unoccupied cells, respectively.

The minimum number of rectangles necessary in this case is 3. (Cover column 1, column 2, and row 3.)

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

解决方案

Consider a bipartite graph consisting of two sets of vertices, with the vertices in the first set corresponding to the rows, and the vertices from the second set corresponding to the columns of the grid. A vertex i from the first set is connected to a vertex j from the second set iff a[i][j] == 'x'.

Then the problem is reduced to finding a minimum vertex cover of this graph, i.e., the smallest set of vertices such that each edge of the graph has at least one of its endpoints present in this set. As the graph is bipartite, a minimum vertex cover can be computed in polynomial time; see this post.

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