Largest square formed in a matrix-dynamic programming

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 1 1 1 0 
0 0 1 2 2 0 
1 1 1 2 3 1

the above given matrix is 5*6 ,

let n=5, be the rows of matrix .

m=6 ,be the columns of the matrix.

we will use dynamic programming :

take a dp(two dimensional array of size (n+1)*(m+1)) and fill the i=0 and j=0 row and colums with zeros.


if the matrix element is zero than fill  dp with zero,else if it is one take the min of  

matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]

than just find the maximun element in the whole 2D array.


 dp filled in th above way is:

0 0 0 0 0 0 0 
0 0 1 0 1 0 1 
0 1 0 1 0 1 0 
0 0 1 1 1 1 0 
0 0 0 1 2 2 0 
0 1 1 1 2 3 1 




here is the c++ implementation:

#include <iostream>
using namespace std;

int main() { int t; cin>>t;
while(t--)
{ int n,m;
 cin>>n>>m;
 
 int dp[n+1][m+1];   int maxele=0;
 for(int i=0;i<n+1;i++)
 { 
     for(int j=0;j<m+1;j++)
     {
         if(i==0 || j==0)
         dp[i][j]=0;
         else
        { cin>>dp[i][j];
           
          if(dp[i][j]!=0)
          {
             int x= min(dp[i-1][j-1],dp[i-1][j]);
             dp[i][j]=min(dp[i][j-1],x)+1;
             
             maxele=max(dp[i][j],maxele);
          }
      
        }
         
     }
     
 }
   
 cout<<maxele<<endl;
 
 
}
	//code
	return 0;
}

here instead of difining a separate matrix we can directly take the input in dp 2D array.

darkmode