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?
The largest square submatrix is formed by cells (0, 2) , (3, 2) , (0, 5) , and (3, 5) . The brute-force solution is to consider every square submatrix and check if it is surrounded by all 1's . We keep track of the dimensions of the largest square submatrix seen and finally return it.
A sub-matrix is a matrix obtained from the given matrix by deletion of several (possibly, zero or all) rows/columns from the beginning and several (possibly, zero or all) rows/columns from the end. A square matrix is a matrix which has the same number of rows and columns.
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:
count=0
count=1
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)
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)
LSBRA(X,Y)
means "Largest Square with Bottom-Right At X,Y"
Pseudocode:
LSBRA(X,Y): if (x,y) == 0: 0 else: 1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )
(For edge cells, you can skip the MIN part and just return 1 if (x,y) is not 0.)
Work diagonally through the grid in "waves", like the following:
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
or alternatively, work through left-to-right, top-to-bottom, as long as you fill in edge cells.
0 1 2 3 4 +---------- 0 | 1 2 3 4 5 1 | 6 7 8 9 . 2 | . . . . . 3 | . . . . .
That way you'll never run into a computation where you haven't previously computed the necessary data - so all of the LSBRA()
"calls" are actually just table lookups of your previous computation results (hence the dynamic programming aspect).
Why it works
In order to have a square with a bottom-right at X,Y - it must contain the overlapping squares of one less dimension that touch each of the other 3 corners. In other words, to have
XXXX XXXX XXXX XXXX
you must also have...
XXX. .XXX .... .... XXX. .XXX XXX. .... XXX. .XXX XXX. .... .... .... XXX. ...X
As long as you have those 3 (each of the LSBRA checks) N-size squares plus the current square is also "occupied", you will have an (N+1)-size square.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With