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) 的辅助数组，并在其每个单元格中存储子矩阵中的个数，左上角为 (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掉出阵列的情况。

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