Biggest Plus Sign in Matrix

 Biggest Plus Sign in Matrix (Dynamic Programming)

PROBLEM STATEMENT :

The program must accept an integer matrix of size R*C containing only 0s and 1s as the input. The program must find the biggest plus sign (+) formed by 1s in the given matrix. Then the program must print the length of the edge of the biggest plus sign (Edge length = the number of cells from the middle cell of the plus sign to one of the four ends). All four edges of the plus sign must be equal. If the plus sign is not present in the matrix, then the program must print -1 as the output.

Boundary Condition(s):

3 <= R, C <= 50

Input Format:

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

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

Output Format:

The first line contains the length of the edge of the biggest plus sign

Example Input/Output 1: 
Input: () 
6 7
0 0 1 0 1 0 1
0 0 1 0 1 0 1
1 1 1 1 1 1 1
0 0 1 0 1 0 0
0 1 1 1 0 0 0
0 0 1 0 0 0 0 
Output: 
3 

Explanation: 

The biggest plus sign formed by 1s in the matrix is highlighted below.

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

Example Input/Output 2: 
Input: () 
4 4
1 0 1 0
1 1 1 0
1 0 1 0
1 1 1 1 
Output: 
-1 

Hint:  We can use Dynamic Programming for the Optimized Solution

---

       

                    

            1)    LEARN THRICE 

                                👇 

            2)    THINK TWICE

                                👇 

            3)    APPLY ONCE

SOLUTION :

C++ (CPP) (Optimized Code)

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

int main(int argc, char** argv)
{
    int r, c;
    cin >> r >> c;
    vector<vector<int>> v(r, vector<int> (c));
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            cin >> v[i][j];
    vector<vector<int>> dp(r, vector<int> (c, min(r,c)));
    for(int i = 0; i < r; i++)
    {
        int rSum = 0;
        for(int j = 0; j < c; j++)
        {
            if(v[i][j] != 0)
                dp[i][j] = rSum ++;
            else
            {
                rSum = 0;
                dp[i][j] = 0;
            }
        }
        rSum = 0;
        for(int j = c-1; j >= 0; j--)
        {
            if(v[i][j] != 0)
            {
                dp[i][j] = min(dp[i][j], rSum);
                rSum ++;
            }
            else
            {
                dp[i][j] = 0;
                rSum = 0;
            }
        }
    }
    for(int j = 0; j < c; j++)
    {
        int rSum = 0;
        for(int i = 0; i < r; i++)
        {
            if(v[i][j] != 0)
                dp[i][j] = min(dp[i][j],rSum++);
            else
            {
                rSum = 0;
                dp[i][j] = rSum;
            }
        }
        rSum = 0;
        for(int i = r - 1; i >= 0; i--)
        {
            if(v[i][j] != 0)
                dp[i][j] = min(dp[i][j], rSum++);
            else
            {
                rSum = 0;
                dp[i][j] = 0;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
            ans = max(ans, dp[i][j]);
    }
    cout << (ans == 0 ? -1 : ans+1);
}
 

PYTHON SOLUTION 1 (Non-Optimized Code)

       
m,n=map(int,input().split()) 
l=[input().split() for i in range(m)] 
max_value=0 
for i in range(m):
    for j in range(n):
        if l[i][j]=='1':
            c=0 
            top,bottom,left,right=i-1,i+1,j-1,j+1 
            while top>=0 and bottom<m and left>=0 and right<n:
                if l[top][j]==l[bottom][j]==l[i][left]==l[i][right]=='1':
                    top,bottom,left,right=top-1,bottom+1,left-1,right+1 
                    c+=1
                else:
                    break 
            if c>max_value:
                max_value=c 
if max_value==0:
    print(-1) 
else:
    print(max_value+1)
 

PYTHON SOLUTION 2 (Optimized Code)

       
r,c=map(int,input().strip().split())
mat=[]
for _ in range(r):
    mat.append(list(map(int,input().strip().split())))
dp=[[0 for _ in range(c)] for _ in range(r)]
ans=0
for row in range(r):
    count=0
    for col in range(c):
        if mat[row][col]==0:
            count=0
        else:
            count+=1
        dp[row][col]=count
    count=0
    for col in reversed(range(c)):
        if mat[row][col]==0:
            count=0
        else:
            count+=1
        dp[row][col]=min(dp[row][col],count)
for col in range(c):
    count=0
    for row in range(r):
        if mat[row][col]==0:
            count=0
        else:
            count+=1
        dp[row][col]=min(dp[row][col],count)
    count=0
    for row in reversed(range(r)):
        if mat[row][col]==0:
            count=0
        else:
            count+=1
        dp[row][col]=min(dp[row][col],count)
        ans=max(ans,dp[row][col])
if ans>1:
    print(ans)
else:
    print(-1)
 

Never Stop Learning !!