algorithm - 在具有值 1 和 0 的矩阵中查找最大的方子矩阵具有值 1

Question

我的 axb 矩阵的值为 1 或 0，我需要找到仅包含 1 的最大方子矩阵。我需要了解如何去做。我的意思是我需要算法。示例:

Matrix is 5x5 [ 1 1 1 1 1
                1 1 1 0 0
                1 1 1 0 0
                1 0 1 1 1
                1 1 1 1 1 ]     largest is 3x3 , starting position 0,0 and return value 3

另一个例子:

Matrix is 5x5 [ 0 1 1 1 1
                0 1 1 1 1
                1 1 1 1 1
                1 1 1 1 1
                1 0 1 0 1 ] 

largest is 4x4 , starting position 0,1 and return value 4

由于程序将由多种编程语言完成，因此我需要一种算法。但是你基本上可以写一个“C”的代码来解释......

Answer 1

我不知道这是否是最佳解决方案，但这是一个简单的想法。

使用 5x5 矩阵并按以下方式从中创建 4x4 矩阵:

每个 2x2 矩阵都变成一个 1x1 矩阵，如果所有原始数字都为 1，则为 1，否则为 - 0。

Matrix is 5x5 [ 1 1 1 1 1
                1 1 1 0 0
                1 1 1 0 0
                1 0 1 1 1
                1 1 1 1 1 ]

将转向

Matrix is 4x4 [ 1 1 0 0
                1 1 0 0
                0 0 0 0
                0 0 1 1 ]

现在我们重复这个过程:

Matrix is 3x3 [ 1 0 0
                0 0 0
                0 0 0 ]

再一次:

Matrix is 2x2 [ 0 0
                0 0 ]

现在全为 0，我们可以搜索仍然包含 1 的最小矩阵。这可以告诉我们原始 1 的矩阵在哪里，矩阵的大小相对于原始矩阵的大小可以告诉我们它有多大。在我们的例子中，它位于 3x3 的左上角，所以最初它是左上角的 3x3 矩阵。

我们正在执行的操作实际上是与 1 的 2x2 矩阵进行卷积，然后向下舍入。许多编程语言都有一个具有此功能的库。

单个卷积的时间复杂度是O(n^2)，但是我们执行这个n次所以时间复杂度是O(n ^3)。

另一个例子:

Matrix is 5x5 [ 0 1 1 1 1
                0 1 1 1 1
                1 1 1 1 1
                1 1 1 1 1
                1 0 1 0 1 ] 

Matrix is 4x4 [ 0 1 1 1
                0 1 1 1
                1 1 1 1
                0 0 0 0 ] 

Matrix is 3x3 [ 0 1 1
                0 1 1
                0 0 0 ] 

Matrix is 2x2 [ 0 1
                0 0 ]

Matrix is 1x1 [ 0 ]

所以 2x2 中的右上角是最后一个左边，这意味着原始图像是 4x4 的右上角。