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!

ex)

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

ans:

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

okay so far i have...

function:

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 inputted into the array)

int main() {

int Sq[5][6]; //5,6 = bottom right conner

int X = Square(Sq[5][6]);

}

haha this seems totally wrong @_@

Answer 1

The first algorithm that comes to my mind is:

1. '&&' column/row 1 with column/row 2 if, this is to say do an '&&' operation between each entry and its corresponding entry in the other column/row.
2. Check the resulting column, if there are any length 2 1's that means we hit a 2x2 square.
3. And the next column with the result of the first two. If there are any length 3 1's we have hit a 3x3 square.
4. Repeat until all columns have been used.
5. Repeat 1-4 starting at column 2.

I won't show you the implementation as its quite straightforward and your problem sounds like homework. Additionally there are likely much more efficient ways to do this, as this will become slow if the input was very large.

Answer 2

OK, the most inefficient way but simple would be:

1. select first item. check if 1, if so you have a 1x1 square.

2. check one below and one to right, if 1, then check row 2 col 2, if 1, 2x2 square.

3. check row 3 col 1, col 2 and col 3, plus row 1 col 3, row 2 col 3, if 1, 3x3.

4. So basically you keep expanding the row and col together and check all the cells inside their boundaries. As soon as you hit a 0, it's broken, so you move along 1 point in a row, and start again.

5. At end of row, move to next row.

6. until the end.

You can probably see how those fit into while loops etc, and how &&s can be used to check for the 0s, and as you look at it, you'll perhaps also notice how it can be sped up. But as the other answer just mentioned, it does sound a little like homework so we'll leave the actual code up to you.

Good luck!

Answer 3

Let input matrix is M: n x m

T[i][j] is DP matrix which contains largest square side with squares bottom right angle (i,j).

General rule to fill the table:

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;

The result square size is max value in T.

Filling T[i][0] and T[0][j] is trivial.

I am not sure if this algo can be used for your huge file, but you don't need to store entire matrix T but only current and previous lines only.

Answer 4

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)

Answer 5

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.