41

我需要在一个充满 1 和 0 的巨型文件中找到最大的 1 正方形。我知道我必须使用动态编程。我将它存储在二维数组中。找到最大正方形的算法的任何帮助都会很棒，谢谢！

示例输入：

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

回答：

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

到目前为止我的代码：

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

（假设值已经输入到数组中）

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

我该如何从那里继续？

4

7 回答 7

81

这是解决方案的草图：

对于每个单元格，我们将保留一个计数器，以使用该单元格作为左上角来制作一个正方形的大小。显然，所有为 0 的单元格都将 0 作为计数。

从右下角的单元格开始迭代并转到左下角，然后向上移动一行并重复。

在每次扫描时执行以下操作：

  1. 如果单元格有 0 分配count=0
  2. 如果单元格有 1 并且是边缘单元格（仅底部或右侧边缘），则分配count=1
  3. 对于所有其他单元格，检查其右侧、右下方和下方的单元格计数。取其中的最小值并加 1 并将其分配给计数。保留一个全局max_count变量以跟踪迄今为止的最大计数。

在遍历矩阵结束时，max_count将具有所需的值。

复杂性不再是遍历矩阵的成本。

这是遍历后矩阵的样子。括号中的值是计数，即可以使用单元格作为左上角的最大正方形。

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

用 Python 实现

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)
于 2009-11-13T02:03:40.617 回答
8

LSBRA(X,Y)表示“X,Y 右下角的最大正方形”

伪代码：

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

（对于边缘单元，您可以跳过 MIN 部分，如果 (x,y) 不为 0，则返回 1。）

在“波浪”中沿对角线穿过网格，如下所示：

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

或者，只要您填写边缘单元格，就可以从左到右、从上到下进行操作。

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

这样，您将永远不会遇到您以前没有计算过必要数据的计算 - 所以所有LSBRA()“调用”实际上只是您以前计算结果的表查找（因此是动态编程方面）。

为什么有效

为了在 X,Y 处有一个右下角的正方形 - 它必须包含与其他 3 个角中的每一个相接触的少一维的重叠正方形。换句话说，拥有

XXXX
XXXX
XXXX
XXXX

你还必须...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

只要你有这 3 个（每个 LSBRA 检查）N 大小的方块加上当前方块也被“占用”，你就会有一个 (N+1) 大小的方块。

于 2009-11-13T02:05:28.883 回答
3

我想到的第一个算法是：

  1. '&&' 列/行 1 和列/行 2 如果，这就是说在每个条目与其在另一列/行中的对应条目之间执行“&&”操作。
  2. 检查结果列，如果有任何长度为 2 1，这意味着我们击中了一个 2x2 正方形。
  3. 下一列是前两列的结果。如果有任何长度为 3 1，我们已经击中了一个 3x3 正方形。
  4. 重复直到所有列都用完。
  5. 从第 2 列开始重复 1-4。

我不会向您展示实现，因为它非常简单，而且您的问题听起来像是家庭作业。此外，可能还有更有效的方法可以做到这一点，因为如果输入非常大，这将变得很慢。

于 2009-11-13T01:56:53.320 回答
2

让输入矩阵为M：nxm

T[i][j]是 DP 矩阵，其中包含最大正方形边和正方形底部直角(i,j)。

填表的一般规则：

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

结果正方形大小是 中的最大值T。

填充T[i][0]和T[0][j]是微不足道的。

我不确定这个算法是否可以用于你的大文件，但你不需要存储整个矩阵T，只需要存储当前行和上一行。

以下注释可以帮助理解一般概念：

  • 所有具有右下角 (i-1, j)、(i, j-1)、(i-1, j-1) 且大小为 s 的正方形都在具有右下角 (i, j) 且大小为 s 的正方形的内部+1。
  • 如果有一个大小为 s+1 且右下角位于 (i, j) 的正方形，则具有右下角的最大正方形的大小 (i-1, j), (i, j-1), (i-1, j-1) 至少为 s。
  • 反之亦然。如果至少一个在 (i-1, j), (i, j-1), (i-1, j-1) 处有下直角的正方形的大小小于 s，则右下角正方形的大小at (i, j) 不能大于 s+1。
于 2009-11-13T02:03:18.340 回答
1

好的，最低效但最简单的方法是：

  1. 选择第一项。检查是否为 1，如果是，则您有一个 1x1 正方形。

  2. 检查下方一个和一个向右，如果为 1，则检查第 2 行第 2 列，如果为 1，则为 2x2 正方形。

  3. 检查第 3 行第 1 列、第 2 列和第 3 列，加上第 1 行第 3 列、第 2 行第 3 列，如果为 1，则为 3x3。

  4. 所以基本上你一直在扩展 row 和 col 并检查它们边界内的所有单元格。一旦你击中 0，它就坏了，所以你沿着 1 点连续移动，然后重新开始。

  5. 在行尾，移动到下一行。

  6. 直到最后。

您可能会看到它们如何适合 while 循环等，以及如何&&使用 s 来检查 0，并且当您查看它时，您可能还会注意到它是如何被加速的。但正如刚才提到的另一个答案，它听起来有点像家庭作业，所以我们将把实际代码留给你。

祝你好运！

于 2009-11-13T02:02:02.353 回答
1

这里的关键是您可以使用动态编程来跟踪区域的根而不是实际区域。

算法如下：

存储一个称为 max-square 的二维整数数组，其中索引 i,j 处的元素表示它所在的正方形的大小，其中 i,j 是右下角。（如果 max[i,j] = 2，则表示索引 i,j 是大小为 2^2 = 4 的正方形的右下角）

对于每个索引 i,j：

如果在 i,j 处元素为 0，则将最大平方 i,j 设置为 0。

别的：

求max-square[i - 1, j] 和 max-square[i, j - 1] 和 max-square[i - 1][j -1] 的最小值。将 max-square[i, j] 设置为 1 + 3 的最小值。归纳起来，您最终将填充 max-square 数组。查找/或跟踪过程中的最大值，返回该值^2。

看看人们提出的这些解决方案： https ://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

于 2016-01-22T13:49:54.687 回答
0

令 N 为二维数组中的单元数。存在一种非常有效的算法来列出所有最大的空矩形。最大的空正方形位于这些空矩形之一内，一旦计算出最大空矩形的列表，创建它就很简单了。可在www.ulg.ac.be/telecom/rectangles找到一篇介绍 O(N) 算法来创建此类列表的论文以及源代码（未优化）。请注意，存在一个证明（见论文），最大空矩形的数量以 N 为界。因此，选择最大的空正方形可以在 O(N) 内完成，总体方法也是 O(N)。在实践中，这种方法非常快。实现非常容易，因为整个代码不应超过 40 行 C 代码（列出所有最大空矩形的算法大约需要 30 行 C 代码）。

于 2013-07-07T21:38:38.720 回答