Largest Submatrix - 1s Diagonal

-

 Largest Submatrix - 1s Diagonal 

PROBLEM STATEMENT :

The program must accept an integer matrix of size R*C containing only 0s and 1s as the input. The program must print the largest square submatrix where all the elements in the top-left to bottom-right diagonal are equal to 1. If two or more such largest square matrices occur, then the program must print the first occurring largest square submatrix as the output. If there is no such square submatrix, then the program must print -1 as the output. 

Boundary Condition(s): 

2 <= R, C <= 50 

Input Format: 

The first line contains R and C separated by a space. 

The next R lines, each contains C integers separated by a space. 

Output Format: 

The lines containing the largest square submatrix where all the elements in the top-left to bottom-right diagonal are equal to 1 

Example Input/Output 1: 
Input: () 

10 10 
1 0 0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 1 0 1 0 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 0 
0 1 0 1 0 1 0 0 0 0 
0 0 1 0 0 0 1 0 0 0 
0 0 0 1 0 0 0 1 0 0 
0 0 0 0 1 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 
Output: 
1 0 0 0 0 0 
0 1 0 0 0 0 
1 0 1 0 0 0 
0 0 0 1 0 0 
1 0 0 0 1 0 
0 1 0 0 0 1

Explanation: 

The largest square submatrix having the only 1s in the top-left to bottom-right diagonal is highlighted below. 

1 0 0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 1 0 1 0 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 0 
0 1 0 1 0 1 0 0 0 0 
0 0 1 0 0 0 1 0 0 0 
0 0 0 1 0 0 0 1 0 0 
0 0 0 0 1 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0  

Example Input/Output 2: 
Input: () 

8 4 
0 0 1 1 
0 0 0 1 
0 1 1 0 
0 1 1 0 
0 0 0 0 
0 0 0 0 
1 0 0 1 
1 1 1 0 
Output: 
1 1 
0 1 

Example Input/Output 3: 
Input: () 

4 4 
0 0 1 1 
1 1 0 0 
0 0 0 1 
0 1 1 0 
Output: 
-1




       
                    


            1)    LEARN THRICE 

                                👇 

            2)    THINK TWICE

                                👇 

            3)    APPLY ONCE




SOLUTION :

C++ (CPP)

       
#include <bits/stdc++.h>
 
using namespace std;

int main(int argc, char** argv) {
    int r, c;
    cin>> r>> c;
    vector<vector<int>> arr(r, vector<int> (c));
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            cin>> arr[i][j];
        }
    }
    int max_sub = 0;
    pair<int, int> res_ind;
    for(int i=1; i<r; i++) {
        for(int j=1; j<c; j++) {
            if(arr[i][j]) {
                arr[i][j] += arr[i-1][j-1];
                if(arr[i][j] > max_sub) {
                    max_sub = arr[i][j];
                    res_ind = {i-arr[i][j]+1, j-arr[i][j]+1};
                }
            }
        }
    }
    if(max_sub <= 1) {
        cout<< -1;
        return 0;
    }
    int x = res_ind.first;
    int y = res_ind.second;
    for(int i=x; i<x+max_sub; i++) {
        for(int j=y; j<y+max_sub; j++) {
            if(arr[i][j]) cout<< 1<< " ";
            else cout<< 0<< " ";
        }cout<< endl;
    }
}


JAVA

       
import java.util.*;
public class Hello {

    public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int r=in.nextInt();
int c=in.nextInt();
int mat[][]=new int[r][c];
for(int i=0;i<r;i++)
{
    for(int j=0;j<c;j++)
    {
        mat[i][j]=in.nextInt();
    }
}
int dp[][]=new int[r][c];
for(int i=0;i<c;i++)
{
    dp[0][i]=mat[0][i];
}
for(int i=0;i<r;i++)
{
    dp[i][0]=mat[i][0];
}
for(int i=1;i<r;i++)
{
    for(int j=1;j<c;j++)
    {
        if(mat[i][j]==1)
        {
            dp[i][j]=dp[i-1][j-1]>0?1+dp[i-1][j-1]:1;
        }
        else
        dp[i][j]=0;
    }
}
int cr=0,cc=0;
int max=1;
for(int i=0;i<r;i++)
{
    for(int j=0;j<c;j++)
    {
        if(max<dp[i][j])
        {
            max=dp[i][j];cr=i;cc=j;
        }
    }
}
if(max==1)
{
    System.out.print(-1);return;
}
for(int i=cr-max+1;i<=cr;i++)
{
    for(int j=cc-max+1;j<=cc;j++)
    {
        System.out.print(mat[i][j]+" ");
    }System.out.println();
}
	}
}


PYTHON

       
r,c=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(r)]
copy=[lst[:] for lst in l]
m=1
for i in range(1,r):
    for j in range(1,c):
        if copy[i][j]==1:
            copy[i][j]=copy[i-1][j-1]+1
        else:
            copy[i][j]=0
        if copy[i][j]>m:
            m=copy[i][j]
            endi=i
            endj=j
if m==1:
    print("-1")
else:
    for i in range(endi-m+1,endi+1):
        print(*l[i][endj-m+1:endj+1])


Never Stop Learning !!


Comments

Post a Comment

Popular posts from this blog

DP (1) - Count number of ways to cover a distance

-
Given a distance n, count total number  of ways to cover the distance with 1, 2 and 3 steps. Input: n = 4 Output: 7 Explantion: Below are the four ways  1 step + 1 step + 1 step + 1 step  1 step + 2 step + 1 step  2 step + 1 step + 1 step   1 step + 1 step + 2 step  2 step + 2 step  3 step + 1 step  1 step + 3 step // C++ program to count number of ways in DP  to cover a distance with 1, 2 and 3 steps  #include<iostream>  using namespace std;  int main() {      int n;     std::cin>>n;     int count[n+1];         // Initialize base values. There is one way to cover 0 and 1      // distances and two ways to cover 2 distance.     count[0]  = 1,  count[1] = 1,  count[2] = 2;         // Fill the count array in from bottom to up manner      for (int i=3; i<=n; i++)  ...
Read more

Zero Insert After K Times One

-
 Zero Insert After K Times One  PROBLEM STATEMENT : Given a bitstream of length N consisting of 0s and 1s, insert 0 after 1 has appeared K times consecutively.  Input Format:  The first line contains N and K separated by a space.  The second line contains the bitstream with 1s and 0s with each value separated by a space.  Output Format:   In the first line, the bitstream with the 0 inserted after 1s has appeared K times with each value separated by a space.  Boundary Conditions:   1 <= K <= 1000  2 <= N <= 1000  Example Input/Output 1: Input: ( ) 12 2 1 0 1 1 0 1 1 0 1 1 1 1 Output: 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 SOLUTION : C (Programming Language) Copy Code #include<stdio.h> #include<stdlib.h> int main() { int n,k,cnt=0,i,j,a[2002]; scanf("%d%d",&n,&k); for(i=0;i<n;++i) { scanf("%d",&a[i]); } //Count of 1 in first step for(i=0;i<k;++i...
Read more

Left Number Twice Right

-
 Left Number Twice Right  PROBLEM STATEMENT : A set of N numbers (separated by one or more spaces) is passed as input to the program. The program must identify the count of numbers C where the number on the left is twice the number on the right.  Boundary Conditions:   3 <= N <= 50  The value of the numbers can be from -99999999 to 99999999  Input Format: The first line will contain the N numbers separated by one or more spaces.  Output Format: The first line contains the value of C.  Example Input/Output 1:   Input: 10 20 5 40 15 -2 -30 -1 60  Output: 2 Explanation: The numbers meeting the criteria are 20, -30  Example Input/Output 2:  Input: 5 90 10 2 5 -4 10 6 5 3  Output: 3 Explanation: The numbers meeting the criteria are 2, 6, 5 SOLUTION : C (Programming Language) Copy Code #include<stdio.h> #include<stdlib.h> int main() { int a[50],n=-1,i,cnt=0; while(scanf("%d",&a[++n...
Read more