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

问题描述

我需要找到的1的最大的广场在一个巨大的文件全1和0的。我知道我必须使用动态规划。我将其存储在二维数组。该算法的任何帮助，找到最大的广场将是巨大的，谢谢！

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

我的code迄今：

My code so far:

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

我如何从那里呢？

How do I go on from there?

推荐答案

下面是解决方案的草图：

Here is a sketch of the solution:

有关每个电池我们将保持的多大的正方形可以使用该细胞作为左上角制成的计数器。显然，以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.

在每个扫描做到这一点：

At each scan do this:

1. 如果小区有0分配数= 0


2. 如果小区有1个是边缘细胞（底部或仅右边缘），分配计数= 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屋！