相关疑难解决方法(0)

给定NxN二进制矩阵(仅包含0或1),我们如何才能找到包含全0的最大矩形？

例:

      I
    0 0 0 0 1 0
    0 0 1 0 0 1
II->0 0 0 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 1 <--IV
    0 0 1 0 0 0
            IV 

对于上面的例子,它是一个6×6的二进制矩阵.在这种情况下,返回值将是单元格1:(2,1)和单元格2:(4,4).得到的子矩阵可以是正方形或矩形.返回值也可以是所有0的最大子矩阵的大小,在该示例中为3×4.

我正在尝试提出一种动态编程算法,该算法在矩阵中找到由相同数字组成的最大子矩阵:

例:

{5 5 8}
{5 5 7}
{3 4 1}

答案:由于矩阵导致4个元素

   5 5 
   5 5   

给定NxNxN二进制数组(仅包含0或1),我们如何获得具有非平凡解的最大长方体,即在O(N ^ 3)？

-

找到在N×N二进制矩阵中仅包含零但在上部维度中的最大矩形是同样的问题.此外,在我的情况下,最大的矩形可以"穿过阵列的边缘",即空间就像是2D矩阵的圆环.

对于2D数组,如果条目是:

00111
00111
11000
00000
00111

'X'描述的解决方案是

00XXX
00XXX
11000
00000
00XXX

我已经完成了NxN二进制数组的计算,并按照http://tech-queries.blogspot.de/2011/03/maximum-中的想法找到了O(N ^ 2)中最大矩形问题的解决方案.area-rectangle-in-histogram.html.但我不知道如何将它应用于3D阵列.

-

解决方案"越过边缘"的3x3x3阵列示例:

111
100
011

111
001
111

011
110
011

解决方案应该是:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX

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

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

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