Cod sursa(job #2941939)

Utilizator divadddDavid Curca divaddd Data 18 noiembrie 2022 16:10:20
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <cstring>
#include <fstream>
#define MAX 202
using namespace std;
int n,m,a[MAX][MAX],v[MAX],dr[MAX],st[MAX],s[MAX],vf,ans;
char ch;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

void stersdrep(int x1, int y1, int x2, int y2){
    for(int i = x1; i <= x2; i++){
        for(int j = y1; j <= y2; j++){
            a[i][j] = 1;
        }
    }
}

void getdrep(){
    /// adauga la ans dreptunghiul de arie maxima si apoi il sterge
    memset(v, 0, sizeof(v));
    memset(dr, 0, sizeof(dr));
    memset(st, 0, sizeof(st));
    memset(s, 0, sizeof(s));
    int maxi = 0, x = 0, y = 0, l1 = 0, l2 = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == 0){
                v[j]++;
            }else{
                v[j] = 0;
            }
        }
        vf = 0;
        v[0] = -1;
        s[vf] = 0;
        for(int j = 1; j <= m; j++){
            while(vf > 0 && v[j] <= v[s[vf]]){
                vf--;
            }
            st[j] = s[vf]+1;
            s[++vf] = j;
        }
        vf = 0;
        v[m+1] = -1;
        s[vf] = m+1;
        for(int j = m; j >= 1; j--){
            while(vf > 0 && v[j] <= v[s[vf]]){
                vf--;
            }
            dr[j] = s[vf]-1;
            s[++vf] = j;
        }
        for(int j = 1; j <= m; j++){
            int arie = v[j]*(dr[j]-st[j]+1);
            if(arie > maxi){
                maxi = arie;
                //cout << "(" << i << ", " << j << ") = " << arie << "; " << v[j] << "\n";
                y = st[j];
                x = i-v[j]+1;
                l1 = v[j];
                l2 = (dr[j]-st[j]+1);
            }
        }
    }
    //cout << maxi << "\n";
    //cout << "(" << x << ", " << y << ", " << l1 << ", " << l2 << ")\n";
    stersdrep(x, y, x+l1-1, y+l2-1);
    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";*/
    ans += maxi;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> ch;
            a[i][j] = (ch-'0');
        }
    }
    getdrep();
    getdrep();
    fout << ans;
    return 0;
}