Dynamic programming - Largest square block

Question

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!

example 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

answer:

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

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?

Answer 1

Here is a sketch of the solution:

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. 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.

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)

Implementation in 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)