填充网格的最小矩形区域数

Question

假设我们有一个网格，并且我们想使用尽可能少的颜色在每个矩形区域上绘制矩形区域。

有些单元格已经被涂成黑色，不能被涂满：

是否有多项式算法可以解决此问题？

经过测试，我发现这种情况的解决方案是9（因为我们需要9种不同的颜色来绘制最小数量的区域来填充整个网格）：

---

贪婪的方法似乎很好用：仅搜索具有最大（白色）区域的矩形并将其绘制，重复此操作直到没有其他要绘制的对象为止，但是我没有测量复杂性或正确性。

Answer 1

以下是一些可以在特定情况下简化此问题的观察结果。首先，在不改变所需区域数量的情况下，可以将相邻的相同行和列缩减为一行或一列，以形成简化的网格：

一个简化的网格，其中没有行或列被分成两个以上的未着色部分（即有两个或多个单独的黑色单元格），有一个最佳解决方案，可以通过使用行或列作为区域（取决于宽度或网格的高度更大）：

区域的数量是minimum(width, height) + number of black cells。

如果简化网格中的边界行或列不包含黑色单元格，则将其用作区域始终是最佳解决方案；将它的某些部分添加到其他区域将需要在边界行或列中至少创建一个附加区域（取决于相邻行或列中黑色单元格的数量）：

这意味着可以通过删除没有黑色单元格的边框行和列来进一步简化网格，并将删除区域的数量添加到区域计数中：

同样，如果一个或多个边界单元格被相邻行或列中的黑色单元格隔离，则所有相连的未着色的相邻单元格都可以视为一个区域：

在每一点你都可以回到以前的规则；例如，在上面的例子中，最右边和最左边的列被变成区域后，我们剩下下面的网格，可以用第一条规则简化，因为底部两行是相同的：

折叠相同的相邻行或列也可以局部应用于网格的孤立部分。下面的例子没有相同的相邻行，但中间部分是孤立的，所以第 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

（可以跳过列表中的某些矩形大小；例如，使用 3x1 大小的区域而不添加第四个孤立单元来获得 4x1 是没有意义的。）

选择一个选项后，您将跳过被您选择的矩形覆盖的单元格，并为下一个单元格尝试每个选项，依此类推...

在大网格上运行它会导致大量的操作选项。但是，在每一点上，您都可以返回检查简化规则是否有帮助。

要查看首先选择最大矩形的贪心算法不能保证最佳解决方案，请考虑以下示例。选择中间的 2x2 正方形将导致具有 5 个区域的解决方案，而存在仅具有 4 个区域的多个解决方案。