7

给定一个 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个这样的块。我想找到所有这些块。

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

我有一个可行的蛮力解决方案，遍历所有可能的矩形，检查它们是否满足前两个标准；然后遍历所有找到的矩形，删除另一个矩形中包含的所有矩形；我可以通过首先删除连续的相同行和列来加快速度。但我相当肯定有一种更快的方法。

4

3 回答 3

1

您可以在考虑每个矩形和适当聪明的解决方案之间找到某个地方。

例如，从每个开始，1您可以创建一个矩形，然后在 4 个方向上逐渐向外扩展其边缘。当您击中 2 时停止，如果 (a) 您必须在所有 4 个方向上停止，并且 (b) 您之前没有见过这个矩形，请记录这个矩形。

然后回溯：您需要能够从1左上角附近开始生成红色矩形和绿色矩形。

不过，这个算法有一些非常糟糕的最坏情况。1脑海中浮现出一个由所有 s 组成的输入。所以它确实需要与其他一些聪明才智或对输入的一些限制相结合。

于 2012-06-12T18:16:23.093 回答
1

考虑更简单的一维问题：

找出.2.1.1...12....2..1.1..2.1..2其中至少包含一个1且没有2且不是该字符串的子串的所有子串。这可以在线性时间内解决，您只需要检查1两个之间是否存在 a 2。

现在您可以轻松地将此算法应用于二维问题：

对于从到的1≤i≤j≤n所有行求和，使用以下定律：, , , , ,并将一维算法应用于结果行。ij.+.=..+1=1.+2=21+1=11+2=22+2=2

复杂度：O(n²m)。

于 2012-06-12T18:35:21.933 回答
1

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

受此答案的启发：https ://stackoverflow.com/a/7353193/145999 （图片也取自那里）

首先，我逐列处理矩阵，创建一个新矩阵 M1 测量到最后一个“1”的步数和一个矩阵 M2 测量到最后一个“2”的步数 M1 & M2

想象上图中任何灰色块中的“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 包含所有具有所需属性的矩形。

于 2012-06-14T19:24:28.677 回答