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,
Leave a Reply