Cod sursa(job #193618)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 5 iunie 2008 14:44:59
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>
#define N 515
char ch,s[N][N];
int v[N][N];
int main(){
    int min,p,r1=0,r2=0,nr,n,m,i,j,h,x,y,x2,y2;
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            scanf("%c",&ch);
            if(ch=='0')
                s[i][j]=1;
            else
                s[i][j]=0;
        }
        scanf("%c",&ch);
    }
    for(j=1;j<=m;++j){
        nr=0;
        for(i=1;i<=n;++i)
			if(s[i][j]==1)
				v[i][j]=++nr;
			else{
				v[i][j]=0;
				nr=0;
			}
    }
    for(i=1;i<=n;++i)
        for(h=1;h<=m;++h){
            nr=0;
			min=v[i][h];
            for(j=h;j<=m;++j){
                ++nr;
                if(v[i][j]<min)
                    min=v[i][j];
                if(!v[i][j]){
                    min=3;
                    nr=0;
                }
                p=min*nr;
                if(p>r1){
                    r1=p;
                    x=i-min+1;   
                    y=j-nr+1;   
                    x2=i;   
                    y2=j;
                }
            }
		}
    for(i=x;i<=x2;++i)
        for(j=y;j<=y2;++j)
            s[i][j]=0;
    for(j=1;j<=m;++j){
        nr=0;
        for(i=1;i<=n;++i)
			if(s[i][j]==1)
				v[i][j]=++nr;
			else{
				v[i][j]=0;
				nr=0;
			}
    }	
    for(i=1;i<=n;++i)
        for(h=1;h<=m;++h){
            nr=0; min=v[i][h];
            for(j=h;j<=m;++j){
                ++nr;
                if(v[i][j]<min)
                    min=v[i][j];
                if(!v[i][j]){
                    min=3;
                    nr=0;
				}
				p=min*nr;
				if(p>r2)
					r2=p;
			}
		}
    printf("%d\n",r1+r2);
	fclose(stdin);
	fclose(stdout);
	return 0;   
}