Maximum size Square sub-with all 1’s in C++

In this tutorial, we are going to discuss how to find maximum square sub-matrix with all 1’s and its size in a given binary matrix in C++. We will use a dynamic programming approach to solve this problem.

What is Dynamic Programming?

Dynamic programming is an approach to solve the complex problem by breaking down into simple sub-problems and store the result of sub-problems for future use. We use DP basically when we have to use a recursive approach for a problem and there is a need to calculate the result of the same sub-problem again and again.

Step by Step Approach

Take two input n and m as rows and columns of input matrix.
Input 2-D binary matrix a[][] of size n*m.
Take an auxiliary 2-D matrix b[][] of size n*m.
Now, input elements of 1st row and 1st column of a[][] as it is in matrix b[][].
Now, fill rest of matrix b[][] as

find maximum square sub-matrix with all 1’s in C++

check every possible square 2*2 matrix and find minimum element among top-left, top-right, bottom-left element and find fill bottom-right element as min. among 3 + 1 else fill the value 0.

Code Snippet:-

if(a[i][j] == 1)
b[i][j] = min(b[i][j-1],min(b[i-1][j], b[i-1][j-1])) + 1;
else
b[i][j] = 0;

Check for maximum value in matrix b[][] and store it in max_num and that row value in max_i and column in max_j.
To print the max square sub-matrix of 1’s backtrack from max_i,max_j and print matrix of max_num*max_num.

C++ Code implementation of maximum square sub-matrix with 1’s

#include<bits/stdc++.h> 

 using namespace std;
 
  int a[100][100];

  void solve(long long n, long long m) 
{ 
  int i,j; 
  int b[100][100]; 

  for(i = 0; i < n; i++) 
  b[i][0] = a[i][0]; 


  for(j = 0; j < m; j++) 
   b[0][j] = a[0][j]; 
  

    for(i = 1; i < n; i++) 
  { 
    for(j = 1; j < m; j++) 
  { 
       if(a[i][j] == 1) 
    b[i][j] = min(b[i][j-1],min(b[i-1][j], b[i-1][j-1])) + 1; 

    else
    b[i][j] = 0; 
  } 
} 


  int max_num = b[0][0], max_i = 0, max_j = 0; 

   for(i = 0; i < n; i++) 
  { 
   for(j = 0; j < m; j++) 
 	{ 
      if(max_num < b[i][j]) 
    { 
      	max_num = b[i][j]; 
        max_i = i; 
        max_j = j; 
      }	 
  }				 
}	 


   cout<<"Maximum size of Sub-matrix with 1's is : "<<max_num<<"*"<<max_num<<endl;
   
   cout<<"\n Max Square sub-matrix with 1's is :"<<endl;

   for(i = max_i; i > max_i - max_num; i--) 
 { 
    	for(j = max_j; j > max_j - max_num; j--) 
  { 
       cout<<a[i][j]; 
  } 
    cout<<endl; 
  } 
}	 



  int main() 
{ 
   long long i,j,n,m;
   
        cin>>n>>m;
   
          for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
               cin>>a[i][j];
        }
        
         solve(n,m);
}

INPUT

8 8
1 1 0 0 1 1 0 1
1 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1

OUTPUT

Maximum size of Sub-matrix with 1's is : 4*4

Max Square sub-matrix with 1's is :
1111
1111
1111
1111

You may also read these,

Maximum size Square sub-with all 1’s in C++

find maximum square sub-matrix with all 1’s in C++

C++ Code implementation of maximum square sub-matrix with 1’s

Leave a Reply Cancel reply