相关疑难解决方法(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   

我有几个大的2D数组,如:

   1   2  3  4  5
   --------------
1 | 0  1  1  1  0
2 | 0  1  1  1  0
3 | 0  1  0  1  1
4 | 0  1  0  1  1

因此,最大的矩形块(按区域)满足==1 从(1,2)开始,其尺寸为(2,3).

如何在没有显式迭代的情况下使用Mathematica找到它？

注意:

只是为了简化您的测试,这是我的一个样本:

matrix = ImageData@Binarize@Import@"http://i.stack.imgur.com/ux7tA.png"