Cod sursa(job #1324240)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 21 ianuarie 2015 23:45:41
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<stdio.h>
#define NMAX 205
FILE *f=fopen("bmatrix.in","r"), *g=fopen("bmatrix.out","w");

long int n, m, a[NMAX][NMAX], s[NMAX][NMAX];
long int nord[NMAX], sud[NMAX]; // linii
long int vest[NMAX], est[NMAX]; // coloane

long int Maxim(long int A, long int B){if(A>B)return A;return B;}

void Citire(){
long int i, j;
char c;

    fscanf(f,"%ld %ld\n",&n,&m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fscanf(f,"%c",&c);
            a[i][j]=c-'0';
        }
        fscanf(f,"\n");
    }

}

void CreareS(){
long int i, j;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s[i][j] = a[i][j] + s[i][j-1] + s[i-1][j] - s[i-1][j-1];
}

long int DS(long int x1, long int y1, long int x2, long int y2){      // determinare suma
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

void CreareNSVE(){
long int l1, l2, c1, c2, lin, col, st, fn, nrcol, nrcolmax, nrlin, nrlinmax, arie, i;

    // NORD si SUD
    for(l1=1;l1<=n;l1++){
        for(l2=l1;l2<=n;l2++){

            nrcol=0; nrcolmax=0;
            for(col=1;col<=m;col++){
                if( DS(l1,col,l2,col)== 0 ){ nrcol++; nrcolmax = Maxim (nrcol,nrcolmax); }
                else nrcol=0;
            }

            arie = (l2-l1+1) * nrcolmax;
            nord[l2] = Maxim(arie,nord[l2]);
            sud [l1] = Maxim(arie,sud [l1]);

        }
    }
    for(i=1;i<=n;i++) nord[i] = Maxim(nord[i],nord[i-1]);
    for(i=n;i>=1;i--) sud [i] = Maxim(sud [i],sud [i+1]);

    // VEST si EST
    for(c1=1;c1<=m;c1++){
        for(c2=c1;c2<=m;c2++){

            nrlin=0; nrlinmax=0;
            for(lin=1;lin<=n;lin++){
                if( DS(lin,c1,lin,c2)== 0 ){ nrlin++; nrlinmax = Maxim (nrlin,nrlinmax); }
                else nrlin=0;
            }

            arie = (c2-c1+1) * nrlinmax;
            vest[c2] = Maxim(arie,vest[c2]);
            est [c1] = Maxim(arie,est [c1]);

        }
    }
    for(i=1;i<=m;i++) vest[i] = Maxim(vest[i],vest[i-1]);
    for(i=m;i>=1;i--) est [i] = Maxim(est [i],est [i+1]);
}

void Aflare(){
long int i, j, ariemax=0;

    for(i=1;i<=n-1;i++) ariemax = Maxim( ariemax, nord[i] + sud[i+1] ); // 1..i, i+1..n
    for(i=1;i<=m-1;i++) ariemax = Maxim( ariemax, vest[i] + est[i+1] ); // 1..i, i+1..m
    fprintf(g,"%ld\n",ariemax);
}

int main(){

    Citire();
    CreareS();
    CreareNSVE();
    Aflare();

return 0;
}