我需要一个算法来解决以下问题(我已经尝试了一些个人解决方案,但它们似乎不是最佳的)
如果给定一个带有标记和未标记区域(以矩阵形式)的表面,以及可以以任何形式或位置操作的 2 个矩形,请找到矩形的可能形状和位置,使其覆盖所有标记区域,同时保持最小表面区域可能。
我需要一个算法来解决以下问题(我已经尝试了一些个人解决方案,但它们似乎不是最佳的)
如果给定一个带有标记和未标记区域(以矩阵形式)的表面,以及可以以任何形式或位置操作的 2 个矩形,请找到矩形的可能形状和位置,使其覆盖所有标记区域,同时保持最小表面区域可能。
首先,找到包围整个区域的矩形。一个算法是这样的(假设原点在左上角):
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
垂直间隙也是如此。然后检查哪个间隙最大。
然后使用最大的间隙作为分隔符将包含所有内容的矩形分成两部分。最后一步是折叠两个矩形(使用顶部算法的逆向)。