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$ Aug 26, 2012 at 22:39

2 Answers 2

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$ Aug 27, 2012 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, 2012 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$ Aug 26, 2012 at 23:43
  • $\begingroup$ ;) I'm really learning how you think the problem. $\endgroup$ Aug 27, 2012 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$ Aug 27, 2012 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$ Aug 27, 2012 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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