Cod sursa(job #1812220)

Utilizator andra1782Andra Alazaroaie andra1782 Data 21 noiembrie 2016 21:58:20
Problema BMatrix Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>
#define MAX 201
char t[MAX][MAX];
int m,n,st[MAX],stanga[MAX],dreapta[MAX],h[MAX];

int skyline(int m, int n){
    int vf,a,max,i,j;

    for(i=1; i<=m; i++)
        st[i]=0;
    st[0]=vf=0;
    for(j=1; j<=m; j++){
        while(vf>0 && h[j]<=h[st[vf]])
            vf--;
        stanga[j]=st[vf];
        st[++vf]=j;
    }
    for(i=1; i<=m; i++)
        st[i]=0;
    vf=0;
    st[0]=m+1;
    for(j=m; j>0; j--){
        while(vf>0 && h[j]<=h[st[vf]])
            vf--;
        dreapta[j]=st[vf];
        st[++vf]=j;
    }
    max=0;
    for(i=1; i<=m; i++){
        a=h[i]*(dreapta[i]-1-stanga[i]);
        if(a>max)
            max=a;
    }
    return max;
}

int dreptunghi_maxim(int l1, int c1, int l2, int c2){
    int a,maxim,i,j,s;

    for(i=1; i<=m; i++)
        h[i]=0;
    a=maxim=0;
    for(j=c1; j<=c2; j++){
        for(i=l1; i<=l2; i++)
            if(t[i][j]==1)
                h[i-l1+1]=0;
            else
                h[i-l1+1]++;
        s=skyline(l2-l1+1,c2-c1+1);
        if(s>maxim)
            maxim=s;
    }
    return maxim;
}

int main(){
    FILE *fin=fopen("bmatrix.in","r");
    FILE *fout=fopen("bmatrix.out","w");
    int i,j,a,max;

    fscanf(fin,"%d%d ",&m,&n);
    for(i=1; i<=m; i++){
        for(j=1; j<=n; j++)
            t[i][j]=fgetc(fin)-'0';
        fgetc(fin);
    }
    max=0;
    for(i=1; i<m; i++){//axa intre linii
        a=dreptunghi_maxim(1,1,i,n)+dreptunghi_maxim(i+1,1,m,n);
        if(max<a)
            max=a;
    }
    for(i=1; i<n; i++){//axa intre coloane
        a=dreptunghi_maxim(1,1,m,i)+dreptunghi_maxim(1,i+1,m,n);
        if(max<a)
            max=a;
    }
    fprintf(fout,"%d\n",max);
    fclose(fin);
    fclose(fout);
    return 0;
}