Cod sursa(job #3128500)

Utilizator Ale_DemianDemian Alexandra Ale_Demian Data 9 mai 2023 17:49:44
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,a[201][201];
char c[201];

struct punct
{
    int x,y;
};
struct dreptunghi
{
    punct c1,c2,c3,c4;
    int arie;
}d[101];

int verif(punct c1,punct c2,punct c3,punct c4)
{
    for(int i=c1.x;i<=c4.x;i++)
        for(int j=c1.y;j<=c4.y;j++)
            if(a[i][j]==1) return 0;
    return 1;
}

int main()
{
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
        fin.getline(c,201);
        for(int j=1;j<=m;j++)
            a[i][j]=c[j-1]-'0';
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            fout<<a[i][j]<<" ";
        fout<<endl;
    }*/
    int k=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                k++;
                int ii=i;
                int jj=j;
                d[k].c1.x=i;
                d[k].c1.y=j;
                while(a[i][jj]==0 && jj<=m)
                {
                    jj++;
                }
                d[k].c2.x=i;
                d[k].c2.y=jj-1;
                while(a[ii][j]==0 && ii<=n)
                {
                    ii++;
                }
                d[k].c3.x=ii-1;
                d[k].c3.y=j;
                d[k].c4.x=ii-1;
                d[k].c4.y=jj-1;
                if(!verif(d[k].c1,d[k].c2,d[k].c3,d[k].c4))
                {
                    d[k].c1.x=0;
                    d[k].c1.y=0;
                    d[k].c2.x=0;
                    d[k].c2.y=0;
                    d[k].c3.x=0;
                    d[k].c3.y=0;
                    d[k].c4.x=0;
                    d[k].c4.y=0;
                    k--;
                }
                else
                {
                    i=ii-1,j=jj-1;
                    d[k].arie=(d[k].c4.y-d[k].c1.y+1)*(d[k].c4.x-d[k].c1.x+1);
                }
            }
        }
    }
  /*  for(int i=1;i<=k;i++)
    {
        fout<<d[i].c1.x<<" "<<d[i].c1.y<<" "<<d[i].c2.x<<" "<<d[i].c2.y<<" "<<d[i].c3.x<<" "<<d[i].c3.y<<" "<<d[i].c4.x<<" "<<d[i].c4.y<<" "<<d[i].arie<<endl;
    }*/
    punct d1,d2,e1,e2;
    int maxi=0;
    for(int i=1;i<k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            d1.x=d[i].c1.x;
            d1.y=d[i].c1.y;
            d2.x=d[i].c4.x;
            d2.y=d[i].c4.y;
            e1.x=d[j].c1.x;
            e1.y=d[j].c1.y;
            e2.x=d[j].c4.x;
            e2.y=d[j].c4.y;
            if((e1.y>=d1.y && e1.y<=d2.y && e2.y>=d1.y && e2.y<=d2.y) || (d1.y>=e1.y && d1.y<=e2.y && d2.y>=e1.y && d2.y<=e2.y) || (e1.x>=d1.x && e1.x<=d2.x && e2.x>=d1.x && e2.x<=d2.x) || (d1.x>=e1.x && d1.x<=e2.x && d2.x>=e1.x && d2.x<=e2.x))
            {
                    if(d[i].arie+d[j].arie>maxi)
                    {
                        maxi=d[i].arie+d[j].arie;
                    }
            }
        }
    }
    fout<<maxi;
    return 0;
}