CHORIV - Editorial

editorial
,
1

Explanation

Refer : Maximum size square sub-matrix with all 1s - GeeksforGeeks
Let us consider the river as the Matrix with 1’s and 0’s . 1 denoting Obstacle and 0 denoting clean river/chocolate.
Now we have to find the maximum size of square sub matrix with all 0’s that means this peice of chocolate will have no 1’s , i.e no obstacle in his chocolate.

Let’s create another matrix dp[n+1][m+1] in which dp(i,j) denotes the maximum size of the sub matrix with all 0’s whose right bottom is a(i,j) or we can say maximum size sub matrix with all 0’s ending at a(i,j).

Now further part is simple , Copy first row and first columns as it is from A[][] to dp[][]
For other entries ,
if a[i][j]==0 holds set dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
else dp[i][j]=0

Find the maximum value in dp matrix , this will be the answer.

Code Solution

#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

int dp[1002][1002];

int findMaxSquareWithAllZeros(int** a, int n,int m)
{

memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
    if(a[i][0]==0)
        dp[i][0]=1;
    
}



for(int i=0;i<m;i++)
{
    if(a[0][i]==0)
        dp[0][i]=1;
}



// cout<<"\n\n";
for(int i=1;i<n;i++)
{
    for(int j=1;j<m;j++)
    {
        if(a[i][j]==0)
        {
            dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
            dp[i][j]=min(dp[i-1][j-1],dp[i][j])+1;
        }
    }
}

int ans=0;
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        ans=max(ans,dp[i][j]);
    }
}




return ans;

}

int main(){

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

cout<<findMaxSquareWithAllZeros(a,n,m);

return 0;

}