c++ - 在方阵中，每个单元格都是黑色或白色。设计一个算法来找到最大子正方形，使得所有 4 个边框都是黑色

Question

给定一个方阵，其中每个单元格都是黑色或白色。设计一个算法来找到最大的子正方形，使得所有 4 个边框都是黑色的。

我有 O(n^2) 算法:

从左到右扫描每一列，对于每一列中的每个单元格，扫描每一行以找到具有后边框的最大子方 block 。

有更好的解决方案吗？

谢谢

Answer 1

O(n^2) 是可能的。我猜这是最佳选择，因为您有 n^2 个单元格。

请注意，任何正方形的左上角和右下角都位于同一条对角线上。

现在如果我们可以在 O(n) 时间内处理每条对角线，我们就会有一个 O(n^2) 时间算法。

假设我们有一个左上角的候选。我们可以计算它下方和右侧的连续黑色单元格的数量，并取两者中的最小值并将其称为 T。

对于右下角的候选，我们可以计算它左边和顶部的连续黑色单元格的数量，并取两者中的最小值，称之为 B。

一旦我们有了 T 和 B 这两个数字，我们就可以判断给定的左上角和右下角的候选是否真的给了我们一个全黑边框的正方形。

现在可以为每个单元格计算这两个数字，在 O(n^2) 时间内通过遍历整个矩阵四次(如何？)。

那么让我们假设这已经完成了。

现在考虑一条对角线。我们的目标是在 O(n) 时间内沿着这条对角线找到左上、右下对。

假设我们在数组 T[1...m] 中计算了 T，其中 m 是对角线的长度。类似地，我们有一个数组 B[1...m]。 T[1] 对应于对角线的左上端，T[m] 对应于右下角。与 B 类似。

现在我们按如下方式处理对角线，对于每个左上候选 i，我们尝试找到一个右下候选 j，它将给出最大的平方。注意 j >= i。另请注意，如果 (i,j) 是候选者，则 (i',j) 不是，其中 i' > i。

请注意，如果 T[i] >= j-i+1 且 B[j] >= j-i+1，则 i 和 j 形成一个正方形。

即T[i] +i - 1 >= j 和 B[j] -j - 1 >= -i。

因此我们形成新的数组，使得 TL[k] = T[k] + k -1 和 BR[k] = B[k] -k - 1.

所以给定两个新数组 TL 和 BR，以及一个 i，我们需要回答以下问题:

What is the largest j such that TL[i] >= j and BR[j] >= -i ?

现在假设我们能够处理范围最大查询的 BR(可以在 O(m) 时间内完成)。

现在给定 TL[i]，在 [i, TL[i]] 范围内，我们找到 BR 的最大值，比如 BR[j1]。

现在，如果 BR[j1] >= -i，我们在 [j1, TL[i]] 范围内找到 BR 的最大值，然后继续这种方式。

一旦我们找到 (TL[i],BR[j]) 候选者，我们就可以忽略 future i 的数组 BR[1...j]。

这使我们能够在 O(n) 时间内处理每个对角线，给出 O(n^2) 总算法。

我省略了很多细节并给出了草图，因为它已经太长了。请随时编辑此说明。

呼。