algorithm - 我怎样才能找到所有连续的子矩阵？

Question

我只是很难弄明白这一点。我保证这不是作业。

给定一个任意大小的矩阵，如下所示((0, 0) 位于左上角):

1 0 0 1 0 0
0 0 1 1 1 0
0 1 1 1 0 0
0 1 1 1 0 0
0 1 0 1 0 0

我一直在努力弄清楚如何找到所有连续子矩阵的坐标。在此示例中，我应该得到如下列表:

[(2, 1), (3, 3)
 (1, 2), (3, 3)]

我很难弄清楚如何得出这样的列表。我知道该算法不会很高效(我猜 O(n^2))，这很好，因为我将使用的矩阵不会那么大。

即使只是给我一个解决这个问题的线索，我们也将不胜感激。

Answer 1

您可以拥有的最佳解决方案是 O(N^4)，因为这是您可以拥有的最大答案大小(如果所有值都是 1)。

要编写一个 O(N^4) 的解决方案，请执行以下操作 - 使用大小为 O(N^2) 的辅助数组，并在其每个单元格中存储子矩阵中 1 的数量，左上角为 ( 0,0) 和给定单元格的右下角。有了这个数组，您就可以不断地使用以下方法计算矩阵 (a,b)(左上)-> (c,d)(右下)中元素的数量:

num_of_ones(a,b,c,d) = helper_matrix[c][d] + helper_matrix[a-1][b-1] -helper_matrix[a-1][d] -helper_matrix[c ][b-1].

注意 a-1 或 b-1 不在数组中的情况。

使用上面的检查是否每个子矩阵只填充了一个(即其中的一个的数量等于子矩阵的大小)。