Cod sursa(job #1325372)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 23 ianuarie 2015 20:49:32
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <cstdio>
#include <fstream>
#define nmax 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char s[nmax][nmax];
int n,m,sol;
int v[nmax][nmax],col[nmax][nmax];
int sus[nmax],jos[nmax];
int x[nmax][nmax],t;


int solve()
{
    fill(sus,sus+nmax,0);
    fill(jos,jos+nmax,0);

    int i,j,i1,i2,x;
    //creaza sume partiale
    for (j=1;j<=m;j++)
            for (i=1;i<=n;i++)
                        col[i][j]=col[i-1][j]+v[i][j];
    //luma cate doua linii
    int col1=0,col2=0;

    for (i1=1;i1<=n;i1++)
            for (i2=i1;i2<=n;i2++) {
                    col1=0;col2=0;
                    for (j=1;j<=m;j++)
                                //verific daca coloana e libera
                                if (v[i1][j]==0&&v[i2][j]==0&&col[i2][j]-col[i1-1][j]==0)
                                                {

                                            if (col1==0) {
                                                    col1=j;
                                                    col2=j;}
                                                    else col2=j;
                                }
                                        else {

                                            if (col1!=0&&col2!=0) {
                                                        x=(i2-i1+1)*(col2-col1+1);
                                                        sus[i2]=max(sus[i2],x);
                                                        jos[i1]=max(jos[i1],x);
                                                    }
                                            col1=0;
                                            col2=0;
                                            }
            if (col1!=0&&col2!=0) {
                            x=(i2-i1+1)*(col2-col1+1);
                            sus[i2]=max(sus[i2],x);
                            jos[i1]=max(jos[i1],x);
                        }
                    //verific maximul
    }
/*
0 0 0 1 1 1
0 0 0 1 0 0
1 1 1 1 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
*/
    for (i=1;i<=n+1;i++) sus[i]=max(sus[i-1],sus[i]);
    for (i=n+1;i>=1;i--) jos[i]=max(jos[i+1],jos[i]);

    for (i=1;i<=n;i++) sol=max(sol,sus[i]+jos[i+1]);
            //actualizez sol
}


int main()
{
    int i,j;
    f>>n>>m;f.get();
    for (i=1;i<=n;i++) f.getline(s[i]+1,nmax);
    for (i=1;i<=n;i++)
            for (j=1;j<=m;j++) v[i][j]=s[i][j]-'0';

    solve();
    //trebuie sa mai rotesc si sa mai verific odata



    t=max(n,m);

    if (n<=m) {
            for (i=1;i<=t;i++)
                    for (j=1;j<=t;j++)
                            x[i][j]=v[t-j+1][i];

            for (i=1;i<=t;i++)
                    for (j=1;j<=t;j++) x[i][j]=x[i][j+m-n];
            swap(n,m);

    }
        else {
            for (i=1;i<=t;i++)
                    for (j=1;j<=t;j++)
                            x[i][j]=v[t-j+1][i];

            for (i=1;i<=t;i++)
                    for (j=1;j<=t;j++) x[i][j]=x[i+n-m-1][j];
            swap(n,m);
            }

    for (i=1;i<=n;i++) for (j=1;j<=m;j++) v[i][j]=x[i][j];



   // for (i=1;i<=n;i++) {for (j=1;j<=m;j++) g<<v[i][j]<<' ';g<<'\n';}




    solve();
    g<<sol<<'\n';


    return 0;
}