找到具有特定属性的所有矩形区域以矩阵

给出的n * m个矩阵的1，2中的可能的值和空：我寻找所有块B（含有之间的所有值找到具有特定属性的所有矩形区域以矩阵

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

（ X0，Y0）和（X1，Y1）），其：

包含至少一个 '1'
不含 '2'
不是另一个块的与上述特性

实施例：

blocks

的红色，绿色和蓝色区域中的所有包含一个 '1'，没有 '2'，而不是一个较大区域的一部分。这张照片当然有3个以上的这种方块。我想找到所有这些块。

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

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

来源

2012-06-12 HugoRune

这些块的所有边将位于图的边缘或与“2”相邻。也许你可以做些什么。 – robert

如果你在这里没有得到很好的答案，你也可以在http://cs.stackexchange.com上提问。 –

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

通过这个答案的启发：https://stackoverflow.com/a/7353193/145999

第一（图片也是从那里取），我去trought矩阵的列，创建一个新的矩阵M1测量的步骤到最后的“1”的数量和矩阵M2测量的步骤，以最后的数字“2” M1 & M2

在任何灰色块的想象一个“1”或“2”在上述图象

到底我有M1和M2寻找像这样：

enter image description here

没有经过M1和M2在倒车时，按行：

enter image description here

我执行下面的算法：

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-14 19:24:28 HugoRune

你可以在考虑每个矩形和一个合适的解决方案之间找到一个位置。

例如，从每个1开始，您可以创建一个矩形，并逐渐向四个方向扩展其边缘。如果（a）你不得不在所有4个方向上停下来，并且（b）你以前没有看过这个矩形，记录下这个矩形。

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

虽然这种算法有一些非常糟糕的最坏情况。包含所有1的输入值得一提。所以它需要与其他一些聪明或者对输入的一些限制相结合。

来源

2012-06-12 18:16:23

该解决方案比OP的朴素算法差很多。 – Thomash

@Thomash：它不是严重的糟糕，例如它比HugoRune的任何输入都没有'1'的速度快得多。所以问题是，我想是否有可能确定好的情况，并有条件地使用它。 –

当然不是，有一些特定情况下你的算法更好。 – Thomash

考虑简单的一维问题：

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

现在可以将这个算法很容易适应两个维度问题：

对于1≤i≤j≤n总和从i到j使用下列法律的所有行：.+.=.，.+1=1，.+2=2，1+1=1，1+2=2，2+2=2并应用一个维度算法到结果行。

复杂性：O（n 2m）。

来源

2012-06-12 18:35:21 Thomash

感谢您的建议。我不确定，但我认为这是O（n³m），因为对于给定的i和j，它已经是O（nm）。尽管如此，仍然最有可能比蛮力更快。 – HugoRune

@HugoRune不，对于给定的i和j，它是O（m），因为它是一维问题。你可能会说它是O（nm），因为你必须计算从i到j的“总和”，但事实并非如此，因为你可以重复使用i，j-1的结果。 – Thomash

找到具有特定属性的所有矩形区域以矩阵

回答

相关问题