Pagini recente » Cod sursa (job #3211508) | Cod sursa (job #65181) | Cod sursa (job #2928281) | Cod sursa (job #573177) | Cod sursa (job #2430413)
#include <bits/stdc++.h>
#define Dim 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int N,M,dp[5][Dim][Dim][Dim],B1[Dim][Dim],B2[Dim][Dim],B3[Dim][Dim],B4[Dim][Dim],V[6],ans;
char A[Dim][Dim];
int main()
{
f>>N>>M; f.get();
for(int i=1;i<=N;i++,f.get())
for(int j=1;j<=M;j++) f>>A[i][j];
for(int i=N;i>=1;i--)
for(int j=M;j>=1;j--)
for(int h=1;i+h-1<=N;h++)
if(A[i+h-1][j]=='0')
{
dp[1][i][j][h]=dp[1][i][j+1][h]+h;
B4[i][j]=max(max(B4[i+1][j+1],B4[i+1][j]),max(B4[i][j+1],dp[1][i][j][h]));
}
else
{
if(h==1)
B4[i][j]=max(max(B4[i+1][j+1],B4[i+1][j]),max(B4[i][j+1],dp[1][i][j][h]));
break;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
int reper=0;
for(int k=1;k<=i;k++)
if(A[k][j]=='0')
{
dp[2][i][j][k]=dp[2][i][j-1][k]+k-reper;
B1[i][j]=max(max(B1[i-1][j],B1[i-1][j-1]),max(B1[i][j-1],dp[2][i][j][k]));
}
else
{
if(k==1)
B1[i][j]=max(max(B1[i-1][j],B1[i-1][j-1]),max(B1[i][j-1],dp[2][i][j][k]));
reper=k;
}
}
for(int i=1;i<=N;i++)
for(int j=M;j>=1;j--)
{
int reper=0;
for(int k=1;k<=i;k++)
if(A[k][j]=='0')
{
dp[3][i][j][k]=dp[3][i][j+1][k]+k-reper;
B2[i][j]=max(max(B2[i-1][j],B2[i-1][j+1]),max(B2[i][j+1],dp[3][i][j][k]));
}
else
{
if(k==1)
B2[i][j]=max(max(B2[i-1][j],B2[i-1][j+1]),max(B2[i][j+1],dp[3][i][j][k]));
reper=k;
}
}
for(int i=N;i>=1;i--)
for(int j=1;j<=M;j++)
{
int reper=0;
for(int k=1;i+k-1<=N;k++)
if(A[i+k-1][j]=='0')
{
dp[4][i][j][k]=dp[4][i][j-1][k]+k-reper;
B3[i][j]=max(max(B3[i+1][j],B3[i+1][j-1]),max(B3[i][j-1],dp[4][i][j][k]));
}
else
{
if(k==1)
B3[i][j]=max(max(B3[i+1][j],B3[i+1][j-1]),max(B3[i][j-1],dp[4][i][j][k]));
reper=k;
}
}
//for(int i=1;i<=N;i++,cout<<'\n')
// for(int j=1;j<=M;j++) cout<<B3[i][j]<<" ";//<<" "<<B2[i][j+1]<<" "<<B3[i+1][j]<<" "<<B4[i+1][j+1]<<" "<<i<<" "<<j<<'\n';
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
V[1]=B1[i][j],V[2]=B2[i][j],V[3]=B3[i][j],V[4]=B4[i][j];
sort(V+1,V+4);//cout<<i<<" "<<j<<" "<<V[3]<<" "<<V[4]<<'\n';
ans=max(ans,V[3]+V[4]);
}
g<<ans;
return 0;
}