找到矩阵中具有某些属性的所有矩形区域

Question

给定一个n*m矩阵,其可能的值为1,2和null:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

我正在寻找所有块B(包含(x0,y0)和(x1,y1)之间的所有值):

• 包含至少一个'1'
• 不包含'2'
• 不是具有上述属性的另一个块的子集

例:

红色,绿色和蓝色区域都包含"1",没有"2",并且不是更大区域的一部分.当然,在这张图片中有超过3个这样的块.我想找到所有这些块.

找到所有这些区域的快速方法是什么？

我有一个工作强力解决方案,迭代所有可能的矩形,检查它们是否符合前两个标准; 然后迭代所有找到的矩形,删除另一个矩形中包含的所有矩形; 我可以通过先删除连续相同的行和列来加快速度.但我相当确定有一种更快的方式.

Answer 1

我终于找到了一个几乎在线性时间内工作的解决方案（有一个小因素取决于找到的区域的数量）。我认为这是最快的解决方案。

受到这个答案的启发：/sf/answers/514723541/（图片也取自那里）

首先，我按列遍历矩阵，创建一个新矩阵 M1 测量到最后一个“1”的步数，创建一个矩阵 M2 测量到最后一个“2”的步数

想象上图中的任何灰色块中有“1”或“2”

最后我的 M1 和 M2 看起来像这样：

不按行反向遍历 M1 和 M2：

我执行以下算法：

 foundAreas = new list()

 For each row y backwards:
     potentialAreas = new List()
     for each column x:
        if M2[x,y]>M2[x-1,y]:
            add to potentialAreas: 
                new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
        if M2[x,y]<M2[x-1,y]:
            for each area in potentialAreas:
                 if area.hasTop and area.hasOne<area.height:
                        add to foundAreas:
                             new Box(Area.left,y-area.height,x,y)
            if M2[x,y]==0: delete all potentialAreas
            else:
                 find the area in potentialAreas with height=M2[x,y] 
                 or the one with the closest bigger height: set its height to M2[x,y]
                 delete all potentialAreas with a bigger height

            for each area in potentialAreas:
                 if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
                 if M2[x,y+1]==0: area.hasTop=true

现在，foundAreas 包含具有所需属性的所有矩形。