dynamic编程 – 最大的方形块

我需要在一个满是1和0的巨大文件中find最大的1的正方形。 我知道我必须使用dynamic编程。 我将它存储在一个2D数组中。 任何帮助algorithmfind最大的广场将是伟大的，谢谢！

示例input：

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]); } 

我怎么从那里继续？

Answer 1

这里是解决scheme的草图：

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

开始从右下方的单元格迭代到左下angular，然后重复上一行。

在每次扫描时，都要这样做

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

遍历matrix的最后， max_count将具有所需的值。

复杂性不再是matrix遍历的代价。

这就是matrix在遍历之后的样子。 圆括号中的值是计数，即可以使用左上方的单元格的最大平方。

 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) 

Answer 2

LSBRA(X,Y)表示“在X，Y下有LSBRA(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) ) 

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

在“波浪”中对angular地穿过网格，如下所示：

  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()调用实际上只是你以前的计算结果（因此dynamic编程方面）的表查询。

为什么它的作品

为了在X，Y上有一个右下angular的正方形，它必须包含一个与其他三个angular相交的less一个重叠的正方形。 换句话说，要有

 XXXX XXXX XXXX XXXX 

你也必须…

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

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

Answer 3

我想到的第一个algorithm是：

1. '&&'列/行1与列/行2如果，这就是说在每个条目和其他列/行中的对应条目之间进行'&&'操作。
2. 检查结果列，如果有任何长度2 1，这意味着我们击中了2×2平方米。
3. 并在第二个结果的下一列。 如果有任何长度的3 1，我们已经击中了3×3的方块。
4. 重复，直到所有列已被使用。
5. 从第2列开始重复1-4。

我不会告诉你这个实现是相当直接的，你的问题听起来像作业。 此外，有可能更有效的方法来做到这一点，因为如果input非常大，这将变得缓慢。

Answer 4

设inputmatrix为M ：nxm

T[i][j]是包含具有正方形底部直angular(i,j)最大正方形的DPmatrix。

一般规则填表：

 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]是微不足道的。

我不确定这个algorithm是否可以用于你的大文件 ，但是你不需要存储整个matrixT而只需要存储当前和之前的行。

下面的注释可以帮助我们理解一般的想法：

• 具有大小为s的右底angular（i-1，j），（i，j-1），（i-1，j-1）的所有正方形都在右下angular（i，j） +1。
• 如果在（i，j）处存在具有右下angular的大小为s + 1的正方形，则具有右下angular（i-1，j），（i，j-1），（i- j-1）至less是s。
• 相反也是如此。 如果在（i-1，j），（i，j-1），（i-1，j-1）处至less有一个具有底部直angular的正方形的大小小于s，则右下angular在（i，j）不能大于s + 1。

Answer 5

好的，最简单的方法是：

1. select第一项。 检查是否1，如果是这样你有一个1×1方块。

2. 检查下面的一个和右边的一个，如果是1，那么检查第2列第2列，如果是1，2X2平方。

3. 检查第3行第1列，第2列和第3列，第1列第3列，第2列第3列，如果第1,3×3列。

4. 所以基本上你不断扩大行和列，并检查边界内的所有单元格。 一旦你打到0，它就会被打破，所以你连续移动1点，然后重新开始。

5. 在行的末尾，移到下一行。

6. 直到最后。

你可能会看到那些适合while循环的东西，以及如何用&& s来检查0，并且当你看着它的时候，你也许会注意到它是如何被加速的。 但正如刚刚提到的其他答案，听起来有点像作业，所以我们将实际的代码留给你。

祝你好运！

Answer 6

这里的关键是你可以使用dynamic编程来跟踪区域的根 ，而不是实际的区域。

algorithm如下：

存储称为max-square的二维数组，其中位于索引i，j处的元素表示其与i所在的平方的大小，j是右下angular。 （如果max [i，j] = 2，则意味着索引i，j是大小为2 ^ 2 = 4的正方形的右下angular）

对于每个索引我，j：

如果在i，j元素为0，则将max-square i，j设置为0。

其他：

find最大平方[i – 1，j]和最大平方[i，j – 1]和最大平方[i – 1] [j -1]的最小值。 设置max-square [i，j]为1 + 3的最小值。最后，您将最终填充最大平方数组。 find/或跟踪过程中的最大值，返回该值^ 2。

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

Answer 7

设N是二维数组中的单元格的数量。 有一个非常有效的algorithm来列出所有最大的空矩形。 最大的空方形在这些空矩形之一内，并且一旦最大空矩形的列表被计算出来，它就变得微不足道了。 可以在www.ulg.ac.be/telecom/rectangles以及源代码（未优化）中find提出O（N）algorithm来创build这种列表的论文 。 注意存在一个certificate（见论文），最大的空矩形的数量是由N限定的。因此，select最大的空方块可以在O（N）中完成，并且整体方法也是O（N）。 在实践中，这种方法非常快。 因为整个代码不应该超过40行C（algorithm列出所有最大空矩形需要大约30行C），所以实现起来非常容易。