如何使用最快的算法找到所有子矩形？

Question

举个例子，假设我们有一个二维数组，例如：

A= [
    [1,0,0],
    [1,0,0],
    [0,1,1]
   ]

任务是找到所有子矩形仅包含零。所以这个算法的输出应该是：

[[0,1,0,2] , [0,1,1,1] , [0,2,1,2] , [0,1,1,2] ,[1,1,1,2], [2,0,2,0] , 
[0,1,0,1] , [0,2,0,2] , [1,1,1,1] , [1,2,1,2]]

其中[ i , j , a , b ]中的i,j为矩形起点坐标，a,b为矩形终点坐标。

我找到了一些算法，例如 Link1 and Link2 但我认为第一个是最简单的算法，我们想要 fastest.For 第二个我们看到该算法只计算矩形而不是 所有子矩形.

问题：
有谁知道这个问题更好或最快的算法？我的想法是使用动态规划，但是如何使用对我来说并不容易。

Answer 1

假设初始数组大小为 c 列 x r 行。

每个 0 都是一个大小为 1x1 的矩形。

现在执行“水平扩张”，即将每个元素替换为其自身及其右侧的最大值，并删除该行中的最后一个元素。例如

1 0 0    1 0
1 0 0 -> 1 0
0 1 1    1 1

每个零现在对应于原始数组中的一个 1x2 矩形。您可以重复此 c-1 次，直到只剩下一列。

1 0 0    1 0    1
1 0 0 -> 1 0 -> 1
0 1 1    1 1    1

零对应于原始数组中的 1xc 个矩形（最初是 c 列）。

对于每个扩张数组，执行类似的“垂直扩张”。

1 0 0    1 0    1
1 0 0 -> 1 0 -> 1
0 1 1    1 1    1
  |       |     |
  V       V     V
1 0 0    1 0    1
1 1 1 -> 1 1 -> 1
  |       |     |
  V       V     V
1 1 1 -> 1 1 -> 1

在这些 rxc 数组中，零对应于所有可能大小的子矩形。（此处，5 个 1x1 尺寸、2 个 2x1 尺寸、2 个 1x2 尺寸和一个 2x2 尺寸。）

检测零和计算膨胀的总工作量是 O(c²r²) 阶的。我想这是最坏情况下的最优。（如果数组不包含零，则无需继续任何扩张。）

如何使用最快的算法找到所有子矩形？

How to find all sub rectangles using fastest algorithm?

algorithm

dynamic-programming