Cod sursa(job #350411)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 23 septembrie 2009 20:28:58
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.33 kb
#include<fstream>
using namespace std;
int n,m,sup[204],inf[204],best_sup[206],best_inf[206],stiva[204],stiva2[205],SUP,INF,sum; char a[205][205],b[210][210];
void rotate()
{
     int i,j,aux;
     
     for (i=1;i<=n;i++)
       for (j=1;j<=m;j++) 
         b[i][j]=a[j][i];
         
     aux=n;
     n=m;
     m=aux;
     
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++) a[i][j]=b[i][j];
}

int main()
{ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
in>>m>>n;
for(int i=1;i<=m;i++)
 for(int j=1;j<=n;j++)
  in>>a[i][j];    
for(int i=1;i<=n;i++) {best_sup[i]=best_inf[i]=0;sup[i]=0;inf[i]=0;}
int best=0,length;SUP=0,INF=0;;

for(int i=2;i<=m+1;i++)
 { for(int j=1;j<=n;j++) if(a[i-1][j]=='1') sup[j]=0;
                           else sup[j]++;
   int poz=1;
                     
   for(int j=1;j<=n;j++) {
          length=1;
           int aux=j-1;
           while(sup[aux]>=sup[j] && aux>=1) {length++;aux--;}
           int arie=length*sup[j];
           if(best_sup[i]<arie) best_sup[i]=arie;
            }  
   for(int j=n;j>=1;j--) {
          length=1;
           int aux=j+1;
           while(sup[aux]>=sup[j] && aux<=n) {length++;aux++;}
           int arie=length*sup[j];
           if(best_sup[i]<arie) best_sup[i]=arie;
            }                                     
                           
        
        if(SUP<best_sup[i]) SUP=best_sup[i];
        else best_sup[i]=SUP;
        }
for(int i=m-1;i>=0;i--)
 { for(int j=1;j<=n;j++) if(a[i+1][j]=='1') inf[j]=0;
                           else inf[j]++;
   int poz=1;
                     
   for(int j=1;j<=n;j++) {
          length=1;
           int aux=j-1;
           while(inf[aux]>=inf[j] && aux>=1) {length++;aux--;}
           int arie=length*inf[j];
           if(best_inf[i]<arie) best_inf[i]=arie;
            }  
   for(int j=n;j>=1;j--) {
          length=1;
           int aux=j+1;
           while(inf[aux]>=inf[j] && aux<=n) {length++;aux++;}
           int arie=length*inf[j];
           if(best_inf[i]<arie) best_inf[i]=arie;
            }                                     
                           
        
        if(INF<best_inf[i]) INF=best_inf[i];
        else best_inf[i]=INF;
        }        
int sum=0;best_sup[0]=0;best_sup[1]=0;best_inf[m]=0;best_inf[m+1]=0;
for(int i=1;i<=m+2;i++)
 {if(sum<best_sup[i]+best_inf[i-1]) sum=best_sup[i]+best_inf[i-1];
    
        }  
rotate();

for(int i=1;i<=n;i++) {best_sup[i]=best_inf[i]=0;sup[i]=0;inf[i]=0;}
 best=0;length;SUP=0;INF=0;;

for(int i=2;i<=m+1;i++)
 { for(int j=1;j<=n;j++) if(a[i-1][j]=='1') sup[j]=0;
                           else sup[j]++;
   int poz=1;
                     
   for(int j=1;j<=n;j++) {
          length=1;
           int aux=j-1;
           while(sup[aux]>=sup[j] && aux>=1) {length++;aux--;}
           int arie=length*sup[j];
           if(best_sup[i]<arie) best_sup[i]=arie;
            }  
   for(int j=n;j>=1;j--) {
          length=1;
           int aux=j+1;
           while(sup[aux]>=sup[j] && aux<=n) {length++;aux++;}
           int arie=length*sup[j];
           if(best_sup[i]<arie) best_sup[i]=arie;
            }                                     
                           
        
        if(SUP<best_sup[i]) SUP=best_sup[i];
        else best_sup[i]=SUP;
        }
for(int i=m-1;i>=0;i--)
 { for(int j=1;j<=n;j++) if(a[i+1][j]=='1') inf[j]=0;
                           else inf[j]++;
   int poz=1;
                     
   for(int j=1;j<=n;j++) {
          length=1;
           int aux=j-1;
           while(inf[aux]>=inf[j] && aux>=1) {length++;aux--;}
           int arie=length*inf[j];
           if(best_inf[i]<arie) best_inf[i]=arie;
            }  
   for(int j=n;j>=1;j--) {
          length=1;
           int aux=j+1;
           while(inf[aux]>=inf[j] && aux<=n) {length++;aux++;}
           int arie=length*inf[j];
           if(best_inf[i]<arie) best_inf[i]=arie;
            }                                     
                           
        
        if(INF<best_inf[i]) INF=best_inf[i];
        else best_inf[i]=INF;
        }        
best_sup[0]=0;best_sup[1]=0;best_inf[m]=0;best_inf[m+1]=0;
for(int i=1;i<=m+2;i++)
 {if(sum<best_sup[i]+best_inf[i-1]) sum=best_sup[i]+best_inf[i-1];
    
        }  
            
out<<sum;
return 0;    
    }