algorithm - 在二维 block 网格中查找矩形

Question

假设我有一个 7x12 的方 block 网格。我们使用颜色“*”、“%”、“@”和一个空单元格“-”。

1 2 3 4 5 6 7
- - - - - - -  1
- - - - - - -  2
% % - - - - -  3
% % - - - - *  4 
% % - - - @ %  5
@ @ @ - - @ %  6
@ @ * * * - *  7
* * * % % % %  8 
% @ @ % * * %  9
% @ % % % % %  10
* * * % % @ @  11
* * @ @ @ @ *  12

我想在这个网格中找到某个最小尺寸的矩形，然后找到我能找到的最大尺寸，然后再变小，直到找不到大于或等于最小尺寸的矩形为止。

在此示例中，考虑最小尺寸 1x4、4x1、2x2，因此 1x3 无效，但 2x3 有效。如果我们想要最大的矩形，我们会找到以下内容:

• 4x1 (4,8)
• 5x1 在 (3,10)
• 2x3 在 (1,3)
• 2x2 在 (6,1)
• 2x2 在 (1,11)
• 4x1 在 (3,12)

请注意，矩形不能在彼此的空间中，它们不能重叠。例如，未提及 (4,10) 处的 2x2 矩形，因为它会与 (3,10) 处的 5x1 矩形重叠。

所有都是完全有效的矩形:它们等于或大于最小尺寸，并且每个矩形的所有 block 都具有相同的颜色。

我想要的是以编程方式执行此操作。当你告诉某人在网格中找到矩形时，他会立即找到它们，而无需考虑。问题是，我怎样才能编写一个执行相同操作的算法？

我考虑过暴力破解，但我需要算法尽可能快地执行，因为它需要在有限的(移动)设备上在非常短的时间内执行很多次。

我在 Internet 上看到很多关于矩形的问题，但我很惊讶这个问题还没有被问到。是我想得太难了还是从来没有人想做这样的事情？

Answer 1

分别调用输入数组W和H的宽和高

1. 运行 this clever O(WH) algorithm用于确定最大矩形，而不是仅跟踪单个最大矩形，对于 W*H 矩阵中的每个 (x, y) 位置记录，(一个或所有)最大矩形的宽度和高度，其左上角是 (x, y)，随时更新这些值。
2. 遍历此矩阵，将其中每个足够大的矩形添加到 max-heap 中按面积排序(宽 * 高)。
3. 从这个堆中读取条目；它们将按面积递减顺序生产。对于左上角为 (x, y) 且宽度为 w 和高度为 h 的每个条目，将矩形中包含的每个 wh 位置标记为 WH 中的“已使用”位数组。从堆中读取矩形时，我们必须丢弃任何包含“已用”方 block 的矩形，以避免产生重叠的矩形。根据“已使用”数组检查每个候选矩形的四个边就足够了，因为候选矩形可以与另一个矩形重叠的唯一其他方式是后一个矩形是否完全包含在它里面，这是不可能的，因为我们正在按面积递减顺序读取矩形。

这种方法是“贪婪的”，因为如果有多种方法可以将纯色区域切割成最大矩形，则它不能保证选择最大的矩形序列。 (例如，可能有几个矩形的左上角位于 (10, 10) 并且面积为 16:16x1、8x2、4x4、2x8、1x16。在这种情况下，一种选择可能会产生更大的矩形“下游”，但我的算法不能保证做出那个选择。)如果有必要，你可以使用回溯找到这个整体最优的矩形系列，尽管我怀疑这在最坏的情况下可能会非常慢。

我提到的最大矩形算法是为单色矩形设计的，但如果您不能使它适应您的多色问题，您可以在开始第 2 步之前简单地为每种颜色运行一次。