以下是一些可以在特定情况下简化此问题的观察结果。首先,在不改变所需区域数量的情况下,可以将相邻的相同行和列缩减为一行或一列,形成一个简化的网格:
一个简化的网格,其中没有行或列被分成两个以上的无色部分(即具有两个或多个单独的黑色单元),具有可以通过使用行或列作为区域来找到的最佳解决方案(取决于宽度或宽度)网格的高度更大):
那么区域的数量就是最小值(宽度,高度)+ 黑色单元格数量.
如果简化网格中的边框行或列不包含黑色单元格,则将其用作区域始终是最佳解决方案;将其某些部分添加到其他区域将需要在边框行或列中至少创建一个附加区域(取决于相邻行或列中黑色单元格的数量):
这意味着可以通过删除没有黑色单元格的边框行和列,并将删除的区域数量添加到区域计数来进一步简化网格:
类似地,如果一个或多个边界单元被相邻行或列中的黑色单元隔离,则所有相连的未着色相邻单元可以被视为一个区域:
在每一点你都可以回到之前的规则;例如在上面的示例中,最右边和最左边的列变成区域后,我们剩下下面的网格,可以使用第一条规则进行简化,因为底部两行是相同的:
折叠相同的相邻行或列也可以局部应用于网格的隔离部分。下面的示例没有相同的相邻行,但中心部分是隔离的,因此第 3 行到第 6 行可以折叠:
左边的第 3 行和第 4 行可以局部折叠,右边的第 5 行和第 6 行可以局部折叠,所以我们最终得到上面第三张图中的情况。这些塌陷的细胞然后作为一个整体。
一旦您无法使用上述规则找到任何进一步的简化,并且您想要检查网格(部分)的每个可能的划分,第一步可能是列出可以使用相应单元格制作的最大矩形尺寸,如下所示他们的左上角;对于上面第一个示例中的简化 6x7 网格,将是:
COL.1 COL.2 COL.3 COL.4 COL.5 COL.6
ROW 1 [6x1, 3x3, 1x7] [5x1, 2x3] [4x1, 1x7] [3x1] [2x5] [1x7]
ROW 2 [3x2, 1x6] [2x2] [1x6] [] [2x4] [1x6]
ROW 3 [6x1, 1x5] [5x1] [4x3, 2x5] [3x3, 1x5] [2x3] [1x5]
ROW 4 [1x4] [] [4x2, 2x4] [3x2, 1x4] [2x2] [1x4]
ROW 5 [6x1, 4x3] [5x1, 3x3] [4x1, 2x3] [3x1, 1x3] [2x1] [1x3]
ROW 6 [4x2] [3x2] [2x2] [1x2] [] [1x2]
ROW 7 [6x1] [5x1] [4x1] [3x1] [2x1] [1x1]
然后,您可以使用这些最大大小为每个单元格生成每个选项;例如对于单元格 (1,1),它们将是:
6x1, 5x1, 4x1, 3x3, 3x2, 3x1, 2x3, 2x2, 2x1, 1x7, 1x6, 1x5, 1x4, 1x3, 1x2, 1x1
(可以跳过列表中的某些矩形大小;例如,在不添加第四个独立单元格以获得 4x1 的情况下使用 3x1 大小的区域是没有意义的。)
选择一个选项后,您将跳过您选择的矩形覆盖的单元格,并尝试下一个单元格的每个选项,依此类推......
在大型网格上运行它会导致大量的操作选项。但是,在每个点上,您都可以返回检查简化规则是否有帮助。
要知道首先选择最大矩形的贪心算法不能保证最佳解决方案,请考虑下面的示例。选择中间的 2x2 正方形将导致具有 5 个区域的解决方案,而存在多个仅具有 4 个区域的解决方案。