Cod sursa(job #23020)

Utilizator cos_minBondane Cosmin cos_min Data 27 februarie 2007 22:18:41
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "bmatrix.in"
#define out "bmatrix.out"
#define dim 301

char a[dim][dim];
int n, m;

int Doit(int,int);
int Doit2(int,int);
int Doit3(int,int);
int Doit4(int,int);

int main()
{
    int ariemax=0;
    ifstream fin(in);
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    //scanf("%d%d",&n,&m);
    fin >> n >> m;
    
    char ch;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        {
            fin >> ch;
            
            if ( ch == '0' ) 
            {
                 a[i][j] = 0;
            }
            else if ( ch == '1' ) a[i][j] = 1;
        }
            
    for ( int j = 1; j <= n; j++ )
    {
        int val = Doit(1,j) + Doit(j+1,n);
        if ( ariemax < val ) ariemax = val;
    }
    
  /*  for ( int j = 1; j <= m; j++ )
    {
        int val = Doit2(1,j) + Doit2(j+1,m);
        if ( ariemax < val ) ariemax = val;
    }*/
    
    printf("%d", ariemax);
}

int Doit(int s, int d)
{
    int tmax = 0;
    int ariem = 0;
     
    for ( int i = s; i < d; i++ )
    {
        for ( int j = i+1; j <= d; j++ )
        {
            int t = 0;
            tmax = 0;
            for ( int k = 1; k <= m; k++ )
            {
                int ok = 1;
                
                for ( int z = i; z <= j; z++ )
                {
                    if ( a[z][k] == 1 ) ok = 0; 
                }
                
                if ( ok == 1 ) t += 1;
                else           
                {
                     if ( tmax < t ) tmax = t;
                     t = 0;
                }
            }
            if ( tmax < t ) tmax = t;
            if ( ariem < (j-i+1)*tmax ) ariem = (j-i+1)*tmax;
        }
    }
    
   return ariem;                      
}

int Doit2(int s, int d)
{
    int tmax = 0;
    int ariem = 0;
     
    for ( int i = s; i < d; i++ )
    {
        for ( int j = i+1; j <= d; j++ )
        {
            int t = 0;
            tmax = 0;
            for ( int k = 1; k <= n; k++ )
            {
                int ok = 1;
                
                for ( int z = i; z <= j; z++ )
                {
                    if ( a[k][z] == 1 ) ok = 0; 
                }
                
                if ( ok == 1 ) t += 1;
                else           
                {
                     if ( tmax < t ) tmax = t;
                     t = 0;
                }
            }
            if ( tmax < t ) tmax = t;
            if ( ariem < (j-i+1)*tmax ) ariem = (j-i+1)*tmax;
        }
    }
    
   return ariem;                      
}