动态规划 - 最大的方块 [英] Dynamic programming - Largest square block

问题描述

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

I need to find the largest square of 1's in a giant file full of 1's and 0's. I know i have to use dynamic programming. I am storing it in a 2D array. Any help with the algorithm to find the largest square would be great, thanks!

示例输入:

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

(假设值已经输入到数组中)

(assuming values already entered into the array)

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

我该如何继续?

推荐答案

这是解决方案的草图:

对于每个单元格，我们将保留一个计数器，记录使用该单元格作为左上角可以制作多大的正方形.很明显，所有为 0 的单元格都会以 0 作为计数.

For each of the cells we will keep a counter of how big a square can be made using that cell as top left. Clearly all cells with 0 will have 0 as the count.

从右下角单元格开始迭代，到左下角，然后向上一行重复.

Start iterating from bottom right cell and go to bottom left, then go to one row up and repeat.

在每次扫描时这样做:

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

1. If the cell has 0 assign count=0
2. If the cell has 1 and is an edge cell (bottom or right edge only), assign count=1
3. For all other cells, check the count of the cell on its right, right-below, and below. Take the min of them and add 1 and assign that to the count. Keep a global max_count variable to keep track of the max count so far.

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

At the end of traversing the matrix, max_count will have the desired value.

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

Complexity is no more that the cost of traversal of the matrix.

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

This is how the matrix will look like after the traversal. Values in parentheses are the counts, i.e. biggest square that can be made using the cell as top left.

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)

这篇关于动态规划 - 最大的方块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！