Pagini recente » Cod sursa (job #2878028) | Cod sursa (job #1528859) | Cod sursa (job #669773) | Cod sursa (job #2942288) | Cod sursa (job #728203)
Cod sursa(job #728203)
#include <fstream>
using namespace std;
const char InFile[]="bmatrix.in";
const char OutFile[]="bmatrix.out";
const int MaxN=205;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,M,up[MaxN];
char A[MaxN][MaxN];
struct node
{
int height,length,prev,next;
};
node nodes[MaxN];
int counts[MaxN][MaxN];
inline int solve(int x1,int y1,int x2,int y2)
{
int sol=0;
for(register int i=y1;i<=y2;++i)
{
up[i]=0;
}
for(register int i=x1;i<=x2;++i)
{
for(register int j=y1;j<=y2;++j)
{
if(A[i][j]=='0')
{
++up[j];
}
else
{
up[j]=0;
}
nodes[j].prev=j-1;
nodes[j].next=j+1;
nodes[j].length=1;
nodes[j].height=up[j];
counts[up[j]][++counts[up[j]][0]]=j;
}
nodes[y2].next=0;
for(register int k=N;k>=0;--k)
{
for(register int l=1;l<=counts[k][0];++l)
{
int x=counts[k][l];
sol=max(sol,nodes[x].length*nodes[x].height);
int left=nodes[x].prev;
int right=nodes[x].next;
int y=left;
if(right==0)
{
if(left==0)
{
break;
}
else
{
y=left;
}
}
else
{
if(left==0)
{
y=right;
}
else
{
if(nodes[left].height>nodes[right].height)
{
y=left;
}
else
{
y=right;
}
}
}
nodes[nodes[x].prev].next=nodes[x].next;
nodes[nodes[x].next].prev=nodes[x].prev;
nodes[y].height=min(nodes[y].height,nodes[x].height);
nodes[y].length+=nodes[x].length;
nodes[x].prev=nodes[x].next=0;
}
counts[k][0]=0;
}
}
return sol;
}
int main()
{
fin>>N>>M;
for(register int i=1;i<=N;++i)
{
fin>>(A[i]+1);
}
fin.close();
int sol=solve(1,1,N,M);
for(register int i=1;i<=N;++i)
{
int tsol=solve(1,1,i,M)+solve(i+1,1,N,M);
if(tsol>sol)
{
sol=tsol;
}
}
for(register int j=1;j<=M;++j)
{
int tsol=solve(1,1,N,j)+solve(1,j+1,N,M);
if(tsol>sol)
{
sol=tsol;
}
}
fout<<sol;
fout.close();
return 0;
}