Cod sursa(job #1262820)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2014 16:17:40
Problema BMatrix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#define NRDIR 4
#define N 0
#define V 1
#define S 2
#define E 3
#define MAXN 200
char m[MAXN+1][MAXN+1];
int h[MAXN+1], stiva[MAXN+1], aux[MAXN+1][MAXN+1], d[NRDIR][MAXN+1], st[MAXN+1], nrlin, nrcol;
inline void algoritm(int e){
    int i, j, dr;
    for(j=1; j<=nrcol; j++){
        h[j]=0;
    }
    for(i=1; i<=nrlin; i++){
        d[e][i]=d[e][i-1];
        for(j=1; j<=nrcol; j++){
            if(m[i][j]=='1'){
                h[j]=0;
            }else{
                h[j]++;
            }
        }
        stiva[0]=0;
        dr=0;
        for(j=1; j<=nrcol; j++){
            while((dr>0)&&(h[stiva[dr]]>=h[j])){
                dr--;
            }
            st[j]=stiva[dr];
            stiva[++dr]=j;
        }
        stiva[0]=nrcol+1;
        dr=0;
        for(j=nrcol; j>0; j--){
            while((dr>0)&&(h[stiva[dr]]>=h[j])){
                dr--;
            }
            if(d[e][i]<h[j]*(stiva[dr]-st[j]-1)){
                d[e][i]=h[j]*(stiva[dr]-st[j]-1);
            }
            stiva[++dr]=j;
        }
    }
}
inline void rotatie(){
    int i, j, e;
    for(i=1; i<=nrlin; i++){
        for(j=1; j<=nrcol; j++){
            aux[i][j]=m[i][j];
        }
    }
    for(i=1; i<=nrcol; i++){
        for(j=1; j<=nrlin; j++){
            m[i][j]=aux[nrlin-j+1][i];
        }
    }
    e=nrlin;
    nrlin=nrcol;
    nrcol=e;
}
inline int maxim(int a, int b){
    if(a>=b){
        return a;
    }
    return b;
}
int main(){
    int i, j, max;
    FILE *fin, *fout;
    fin=fopen("bmatrix.in", "r");
    fout=fopen("bmatrix.out", "w");
    fscanf(fin, "%d%d", &nrlin, &nrcol);
    for(i=1; i<=nrlin; i++){
        fgetc(fin);
        for(j=1; j<=nrcol; j++){
            m[i][j]=fgetc(fin);
        }
    }
    for(i=0; i<NRDIR; i++){
        algoritm(i);
        rotatie();
    }
    max=0;
    for(i=0; i<=nrlin; i++){
        if(max<d[N][i]+d[S][nrlin-i]){
            max=d[N][i]+d[S][nrlin-i];
        }
    }
    for(j=0; j<=nrcol; j++){
        if(max<d[V][j]+d[E][nrcol-j]){
            max=d[V][j]+d[E][nrcol-j];
        }
    }
    fprintf(fout, "%d\n", max);
    fclose(fin);
    fclose(fout);
    return 0;
}