All ones dp problem edge case

#1

code
#include
using namespace std;

int main() {
// your code goes here
long long int table[1000][1000],prow[1000][1000],pcol[1000][1000],i,j,k,l,m,n,o,p,q,r,s,t;
cin>>m>>n;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>table[i][j];
}
}
for(i=0;i<m;i++)
{
prow[i][n-1]=n;
}
for(i=0;i<n;i++)
{
pcol[m-1][i]=m;
}
for(i=0;i<m;i++)
{
long long int last_col=n;
for(j=n-1;j>=0;j–)
{
if(table[i][j]==0)
{
prow[i][j]=j;
last_col=j;
}
else
{
prow[i][j]=last_col;
}
}
}

for(j=0;j<n;j++)
{
	long long int last_col=m;
	for(i=m-1;i>=0;i--)
	{
		if(table[i][j]==0)
		{
			pcol[i][j]=i;
			last_col=i;
		}
		else
		{
			pcol[i][j]=last_col;
		}
	}
}

/* for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cout<<prow[i][j]<<" “;
}
cout<<endl;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cout<<pcol[i][j]<<” ";
}
cout<<endl;
}*/
long long int x_max=0;
for(i=0;i<m;i++)
{
j=0;

  while(j<n)
  {
  if(table[i][j]==0)
  {
  j++;
  continue;
  }
    l=prow[i][j];
    long long int x_min=1000000;
    for(k=j;k<l;k++)
    {
    	o=pcol[i][k];
    	x_min=min(o-i,x_min);
    }
    x_min=min(x_min,l-j);
     x_max=max(x_min,x_max);
     j++;
  }
 
}
cout<<x_max<<endl;
return 0;

}

ISSUE:---->Actually I am facing problem inn ALLONES DP PROBLEM IN THE PRATICE CHALLENGES OF THE COURSE PLEADE HELP ME IN GETTING IN WHICH SPECIAL CASE MY CODE IS GETTING WRONG ANSWER BECAUSE 3 OUT OF 4 TEST CASES ARE PASSING AND ONLY 1 IS REMAINING PLEASE HELP …

#2

Why are you writing so complicated code. Your dp state will be
if at position a(i,j) then dp[i][j]=a[i][j] + min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]});
i.e all you have to do is take minimum of three mentioned dp state and add that a[i][j] to it , otherwise the state wil be dp[i][j]=0;
You can see my implementation for further understanding.

#3

BUT According to me precomputing the position of next 0’s will also work over here Why cannot I do by that method?

#4

What is use of precomputing next zero , you have to deal with all ones in a submatrix , zero will discard that condition.

#5

Paste your code in cb.lk/ide and save there and send that link.
I will particulary tell you where you are going wrong.

#6

code link http://ideone.com/vt14N5

#7

Bro your code is complicated and without comments , you can try to fill the 2-D dp and you will get the dp state logic i had sent you previously.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.