在2d块网格中查找矩形

Question

假设我有一个块网格,7x12.我们使用颜色'*','%','@'和一个空单元' - '.

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 at(4,8)
• 5x1 at(3,10)
• 2x3 at(1,3)
• 2x2 at(6,1)
• 2x2 at(1,11)
• 4x1 at(3,12)

请注意,矩形不能在每个其他空间中,它们不能重叠.例如,未提及(4,10)处的2x2矩形,因为它将与(3,10)处的5x1矩形重叠.

所有都是完全有效的矩形:它们等于或大于最小尺寸,每个矩形的所有块都是相同的颜色.

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

我考虑过强制但我需要算法尽可能快地执行,因为它需要在有限(移动)设备上的非常小的时间帧内执行很多.

我在互联网上看到很多关于矩形的问题,但是我很惊讶这个问题还没有被问过.我觉得太难了,或者没有人想做过这样的事情？

Answer 1

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

1. 运行这个聪明的O(WH)算法来确定最大的矩形,但不是仅跟踪单个最大的矩形,而是为W*H矩阵中的每个(x,y)位置记录(一个或全部)的宽度和高度左上角为(x,y)的最大矩形,随时更新这些值.
2. 循环遍历此矩阵,将每个足够大的矩形添加到按区域(宽度*高度)排序的最大堆中.
3. 读取此堆中的条目; 它们将以递减的面积顺序生产.对于其左上角为(x,y)并且具有宽度w和高度h的每个条目读取,将矩形中包括的每个w h位置标记为W H位阵列中的"已使用".从堆中读取矩形时,我们必须丢弃任何包含"已使用"方块的矩形,以避免产生重叠的矩形.只需检查每个候选矩形的四个边缘与"已使用"数组是否足够,因为候选矩形与另一个矩形重叠的唯一另一种方式是,如果后一个矩形被它完全包含,这是不可能的,因为事实上,我们正在以递减的区域顺序读取矩形.

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

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