Dynamic programming - Largest square block

Viewed 34513

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?

7 Answers
Related