algorithm - 网格中具有公共(public)角的所有矩形

Question

我想采用 0 和 1 的网格，并得到网格中存在的所有矩形，它们共享一个公共(public)角。

类似于最大矩形问题 - Link 1 Link 2

但是我不想找到一个具有最大面积的矩形，而是想找到共享一个公共(public)角的所有矩形。 IE 如果我指定坐标 (10,10)，我希望所有可能的矩形的左下角都是 10,10。

有人可以帮助解释我如何调整我链接的算法的实现来执行我描述的操作吗？

Answer 1

我不确定如何针对这个问题调整给定的算法，但我有解决这个问题的好方法。

比如说，我们在 (x1, y1) 处得到了矩形的左下角。我们记录矩形的数量(值为 1 并共享左下角)num 和一个水平值，直到在这个 y hval 值处可以找到哪些矩形。现在，我们水平遍历直到 hval 或如果我们在途中找到 0，因为不能在该点之外制作矩形。现在，我们将这个 x 设为新的 hval。我们移动到下一行，每次都做同样的事情，计算我们经过的矩形数。

解决方案是 O(n2)。由于我们最多使用 2*num 步，因此解决方案的复杂性也受 θ(num) 的限制。

此 python 代码示例可以提供更好的理解:

num = 0
hval = len(board)
i = 1
x1=1
y1=1
x2 = x1
while (y1 < len(board) and i > 0):
    i = 0
    while (board[y1][x2] == 1 and x2 < hval):
        num += 1
        x2 += 1
        i += 1
    else:
        hval = x2
        y1 += 1
        x2 = x1
print(num)