4

我需要一个算法来解决以下问题(我已经尝试了一些个人解决方案,但它们似乎不是最佳的)

如果给定一个带有标记和未标记区域(以矩阵形式)的表面,以及可以以任何形式或位置操作的 2 个矩形,请找到矩形的可能形状和位置,使其覆盖所有标记区域,同时保持最小表面区域可能。

4

1 回答 1

3

这个答案是假设你不能旋转矩形并且边总是平行于 x 和 y 轴。

首先,找到包围整个区域的矩形。一个算法是这样的(假设原点在左上角):

For each marked spot in the matrix:
    if spot.x < rectangle.left:
        rectangle.left = spot.x
    if spot.x > rectangle.right:
        rectangle.left = spot.x
    if spot.y < rectangle.top:
        rectangle.left = spot.x
    if spot.y < rectangle.bottom:
        rectangle.left = spot.x

然后,像这样找到最大的水平间隙:

largest_gap = -1
For each column in matrix:
     last_marked_spot = 0, 0
     For each spot in column:
         if spot.marked:
             if spot.x - last_marked_spot.x > largest_gap:
                 largest_gap = spot.x - last_marked_spot.x
             last_marked_spot = spot

垂直间隙也是如此。然后检查哪个间隙最大。

然后使用最大的间隙作为分隔符将包含所有内容的矩形分成两部分。最后一步是折叠两个矩形(使用顶部算法的逆向)。

于 2011-11-08T14:10:02.643 回答