Problem contest with matrix and DP

Question

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.

Answer 1

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.

Answer 2

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;
}