Cod sursa(job #2771189)

Utilizator Emilia23Dobra Emilia Emilia23 Data 25 august 2021 21:55:27
Problema BMatrix Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int a[205][205],n,m,st[205],sol[4][205];
char s[205][205],aux[205][205];

// functie rotire matrice de caractere (pentru ca nu ii modificam elementele)
void rotire90()
{
    int i,j;

    for(i=1;i<=m;i++)
    {
        for(j=n;j>=1;j--)
            aux[i][n-j+1]=s[j][i];
    }
    swap(n,m);

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        s[i][j]=aux[i][j];
}

void matmax(int p)
{
   int i,j,arie,solutie;

   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
   {
       if(s[i][j]=='0')
          a[i][j]=a[i-1][j]+1;
       else a[i][j]=0;
   }


   for(i=1;i<=n;i++)
    {
        int k=1;
        st[k]=0;
        solutie=0;
        for(j=1;j<=m+1;j++)
        {
            while(a[i][j]<=a[i][st[k]] && k>=1)
            {
                arie = a[i][st[k]]*(j-st[k-1]-1);
                solutie=max(solutie,arie);
                k--;
            }
            st[++k]=j;
        }

        sol[p][i]=solutie;
    }
    if(p==1)
   {
       p--;
       p++;
   }
}

int main()
{
    int i,j;

    f>>n>>m;

    for(i=1;i<=n;i++)f>>s[i]+1;

    //sus
    matmax(0);

    rotire90();

    //stanga
    matmax(1);

    rotire90();

    //jos
    matmax(2);

    rotire90();

    //dreapta
    matmax(3);

    int rez=0;

    for(i=1;i<m;i++)
       rez=max(rez,sol[0][i]+sol[2][m-i]);
    for(i=1;i<n;i++)
       rez=max(rez,sol[1][i]+sol[3][n-i]);

    g<<rez;

}