Maximum size Square sub-with all 1’s in C++
By Ravi RajIn 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,
Leave a Reply