Cod sursa(job #253289)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 17:07:23
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
 #include<stdio.h>  
 #define N 515  
 char ch,s[N][N];  
 int v[N][N];  
 int main(){  
     int min,p,r1=0,r2=0,nr,n,m,i,j,h,x,y,x2,y2;  
     freopen("bmatrix.in","r",stdin);  
     freopen("bmatrix.out","w",stdout);  
     scanf("%d%d\n",&n,&m);  
     for(i=1;i<=n;++i){  
         for(j=1;j<=m;++j){  
             scanf("%c",&ch);  
             if(ch=='0')  
                 s[i][j]=1;  
             else  
                 s[i][j]=0;  
         }  
         scanf("%c",&ch);  
     }  
     for(j=1;j<=m;++j){  
         nr=0;  
         for(i=1;i<=n;++i)  
             if(s[i][j]==1)  
                 v[i][j]=++nr;  
             else{  
                 v[i][j]=0;  
                 nr=0;  
             }  
     }  
     for(i=1;i<=n;++i)  
         for(h=1;h<=m;++h){  
             nr=0;  
             min=v[i][h];  
             for(j=h;j<=m;++j){  
                 ++nr;  
                 if(v[i][j]<min)  
                     min=v[i][j];  
                 if(!v[i][j]){  
                     min=3;  
                     nr=0;  
                 }  
                 p=min*nr;  
                 if(p>r1){  
                     r1=p;  
                     x=i-min+1;     
                     y=j-nr+1;     
                     x2=i;     
                     y2=j;  
                 }  
             }  
         }  
     for(i=x;i<=x2;++i)  
         for(j=y;j<=y2;++j)  
             s[i][j]=0;  
     for(j=1;j<=m;++j){  
         nr=0;  
         for(i=1;i<=n;++i)  
             if(s[i][j]==1)  
                 v[i][j]=++nr;  
             else{  
                 v[i][j]=0;  
                 nr=0;  
             }  
     }     
     for(i=1;i<=n;++i)  
         for(h=1;h<=m;++h){  
             nr=0; min=v[i][h];  
             for(j=h;j<=m;++j){  
                 ++nr;  
                 if(v[i][j]<min)  
                     min=v[i][j];  
                 if(!v[i][j]){  
                     min=3;  
                     nr=0;  
                 }  
                 p=min*nr;  
                 if(p>r2)  
                     r2=p;  
             }  
         }  
     printf("%d\n",r1+r2);  
     fclose(stdin);  
     fclose(stdout);  
     return 0;     
}