Cod sursa(job #23037)

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

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

int a[dim][dim];
int coloana[dim][dim], linie[dim][dim];
int n, m;

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

int main()
{
    freopen(out,"w",stdout);
    ifstream fin(in);
    int ariemax=0;
    int tmax=0;
    
    fin >> n >> m;
    
    char c;
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 1; j <= m; j++ )
        {
            fin >> c;
            a[i][j] = (int)c - 48;
            coloana[i][j] = coloana[i-1][j] + a[i][j];
            linie[i][j] = linie[i][j-1] + a[i][j];
        }
	}
            
    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 = 1;
     
    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;
                
                if ( coloana[j][k] - coloana[i-1][k] != 0 ) 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;
                
                if ( linie[k][j] - linie[k][i-1] != 0 ) 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;                      
}