4
$\begingroup$

I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this:

$$\begin{bmatrix} 1 &1 &1 &0\\ 1 &1 &1 &1\\ 0 &0 &1 &0\\ 1 &1 &1 &1 \end{bmatrix}$$

Now you have to find the biggest square matrix inside the original matrix which is filled with only 1's. In my example, take the matrix of $((1,1)$ to $(2,2)$ $$ \begin{bmatrix} 1 & 1\\ 1 &1 \end{bmatrix} $$

But, we might have to deal with matrices of size 1000X1000 as well. So the algorithm should be efficient and use DP, although I don't know if there is other solution. My Teacher told me that it can be done by Dynamic Programming. But I didn't understand his method.

$\endgroup$
1
  • $\begingroup$ Is overlapping possible in this particular problem or not? Because then you could have an even greater matrix, starting at (4,1) and ending at (2,3). $\endgroup$ – Dávid Natingga Aug 26 '12 at 22:39
6
$\begingroup$

An $O(n^2)$ algorithm is possible.

Let $A$ be the given matrix.

You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$

Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$

as

$$S(i+1,j+1) = \min \{S(i,j), S(i+1,j), S(i,j+1)\} + 1 \quad \text{if}\quad A[i+1,j+1] = 1$$

and

$$S(i+1,j+1) = 0 \ \text{if }\ A[i+1,j+1] = 0$$

There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.

$\endgroup$
2
  • $\begingroup$ Which are the others algorithms that you means? I don't know them. Thanks. $\endgroup$ – jonaprieto Aug 27 '12 at 17:44
  • $\begingroup$ @d555: They are too complicated to type here. The basic idea is figure out in $O(n)$ time the maximum rectangle with an edge along a given row. Do this for each row and pick the max. $\endgroup$ – Aryabhata Aug 27 '12 at 18:38
1
$\begingroup$

The following finds the largest matrix dynamically in $O(n^3)$.
The algorithm first reads from the standard input which matrices of dimension 1x1 have all ones. Then it computes all the matrices of dimension 2x2 that have all ones. Then all 3x3 matrices, etc. up to all the n by n matrices (just one) that have all the ones.
When determining whether an i by i matrix has all ones you could check all 1x1 matrices in it if they all are ones. But we have already found all the (i-1) by (i-1) matrices that have ones! So you do not need to check all ones in a (i-1) by (i-1) submatrix again. Just find whether the whole submatrix has all the ones from a has_all_ones array. Every matrix of dimension dim greater than 2 is fully covered by 4 submatrices of dimension dim-1 (it is their union). If these have all ones, the whole matrix of size dim has ones everywhere.

#include<stdio.h>
#include<iostream>

#define MAX 100
using namespace std;

int main(){  
    int n;    
    cin>>n;

    //has_all_ones[dim][row][col] is true if and only if a matrix of size dim
    //starting at positions (row,col) has all ones in it
    bool has_all_ones[MAX][MAX][MAX];//dim, row, col
    for(int row=0; row<n; row++)
        for(int col=0; col<n; col++)
            cin>>has_all_ones[1][row][col];

    //compute dynamically all the matrices with all ones           
    for(int dim=2; dim<=n; dim++)
        for(int row=0; row+dim-1<n; row++)
            for(int col=0; col+dim-1<n; col++){
                //now we do not have to check all the ones in a matrix
                //only the four submatrices
                has_all_ones[dim][row][col] =
                has_all_ones[dim-1][row][col] &&
                has_all_ones[dim-1][row+1][col] &&
                has_all_ones[dim-1][row][col+1] &&
                has_all_ones[dim-1][row+1][col+1];                
            }

     //find the largest one
     for(int dim=n; dim>0; dim--)
        for(int row=0; row+dim-1<n; row++)
            for(int col=0; col+dim-1<n; col++)
                if(has_all_ones[dim][row][col]){
                    cout<<"The largest matrix starts at ("<<row<<", "<<col<<") and ends at ("<<row+dim-1<<","<<col+dim-1<<")."<<endl;
                    return 0;
                }                     

    return 0;
}
$\endgroup$
4
  • $\begingroup$ If you worry about the memory in cases where n=1000, you can delete all the matrices of the dimensions you do not need anymore as you go. Of course, after you have checked that among them is not the largest one. $\endgroup$ – Dávid Natingga Aug 26 '12 at 23:43
  • $\begingroup$ ;) I'm really learning how you think the problem. $\endgroup$ – jonaprieto Aug 27 '12 at 1:23
  • 2
    $\begingroup$ It would be better if you gave an explanation along with the code. Perhaps add the actual recurrence used. $\endgroup$ – Nicholas Mancuso Aug 27 '12 at 2:06
  • $\begingroup$ I think O(n^3) is going to be too slow for a programming competition, you will need at least 10^9 memory references at about 100ns each which is around 10 seconds or so. $\endgroup$ – Andrew Tomazos Aug 27 '12 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.