Pagini recente » Cod sursa (job #652880) | Cod sursa (job #1908117) | Cod sursa (job #255302) | Cod sursa (job #1945955) | Cod sursa (job #1815318)
#include <stdio.h>
#define MAX 201
#define maxim(a,b) a<b ? b:a
char t[MAX][MAX];
int m,n,st[MAX],stanga[MAX],dreapta[MAX],hl1[MAX],hc1[MAX],hl2[MAX],hc2[MAX],l1[MAX],c1[MAX],l2[MAX],c2[MAX];
int skyline(int m, int n, int h[]){
int vf,a,max,i,j;
for(i=1; i<=m; i++)
st[i]=0;
st[0]=vf=0;
for(j=1; j<=m; j++){
while(vf>0 && h[j]<=h[st[vf]])
vf--;
stanga[j]=st[vf];
st[++vf]=j;
}
for(i=1; i<=m; i++)
st[i]=0;
vf=0;
st[0]=m+1;
for(j=m; j>0; j--){
while(vf>0 && h[j]<=h[st[vf]])
vf--;
dreapta[j]=st[vf];
st[++vf]=j;
}
max=0;
for(i=1; i<=m; i++){
a=h[i]*(dreapta[i]-1-stanga[i]);
if(a>max)
max=a;
}
return max;
}
int main(){
FILE *fin=fopen("bmatrix.in","r");
FILE *fout=fopen("bmatrix.out","w");
int i,j,a,max;
fscanf(fin,"%d%d ",&m,&n);
for(i=1; i<=m; i++){
for(j=1; j<=n; j++)
t[i][j]=fgetc(fin)-'0';
fgetc(fin);
}
for(i=1; i<m; i++){
for(j=1; j<=n; j++)
if(t[i][j]==0)
hc1[j]++;
else
hc1[j]=0;
l1[i]=maxim(skyline(n,i,hc1),l1[i-1]);
}
for(i=1; i<n; i++){
for(j=1; j<=m; j++)
if(t[j][i]==0)
hl1[j]++;
else
hl1[j]=0;
c1[i]=maxim(skyline(m,i,hl1),c1[i-1]);
}
for(i=m-1; i>0; i--){
for(j=n; j>0; j--)
if(t[i+1][j]==0)
hc2[j]++;
else
hc2[j]=0;
l2[i]=maxim(skyline(n,m-i,hc2),l2[i+1]);
}
for(i=n-1; i>0; i--){
for(j=m; j>0; j--)
if(t[j][i+1]==0)
hl2[j]++;
else
hl2[j]=0;
c2[i]=maxim(skyline(m,n-i,hl2),c2[i+1]);
}
max=0;
for(i=1; i<m; i++)
if(max<l1[i]+l2[i])
max=l1[i]+l2[i];
for(i=1; i<n; i++)
if(max<c1[i]+c2[i])
max=c1[i]+c2[i];
fprintf(fout,"%d\n",max);
fclose(fin);
fclose(fout);
return 0;
}