Cod sursa(job #3268451)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 15 ianuarie 2025 12:00:11
Problema BMatrix Scor 32
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 202, M_MAX = 202;
int N, M;
int m[N_MAX][M_MAX]; // m[i][j] = 2 => avem un 0 deja folosit
int lin[N_MAX][M_MAX], col[N_MAX][M_MAX];
int used[N_MAX][M_MAX]; // = suma partiala pe matrice pt nr de celule de 2
char s[M_MAX];

pair<int, int> bestRec[N_MAX][M_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M;
    cin.getline(s, M_MAX);
    for(int i = 1, j; i <= N; i++)
    {
        cin.getline(s + 1, M_MAX);
        for(j = 1; j <= M; j++)
            m[i][j] = s[j] - '0';
    }
}

inline int CalcUsed(int r1, int c1, int r2, int c2)
{
    return used[r2][c2] - used[r2][c1-1] - used[r1-1][c2] + used[r1-1][c2-1];
}

int FindMaxRecArea()
{
    int maxArea = 0;
    pair<int, int> pos = make_pair(0, 0);

    for(int i = 1, j; i <= N; i++)
        for(j = 1; j <= M; j++)
        {
            used[i][j] = used[i-1][j] + used[i][j-1] - used[i-1][j-1] + (m[i][j] == 2);

            //cerr << i << ' ' << j << ' ' << used[i][j] << '\n';

            if(m[i][j] == 1)
            {
                lin[i][j] = col[i][j] = 0;
                bestRec[i][j] = make_pair(0, 0);
            }
            else /// if m[i][j] = 0 sau 2
            {
                lin[i][j] = lin[i][j-1] + 1;
                col[i][j] = col[i-1][j] + 1;

                int r = min(bestRec[i-1][j-1].first + 1, lin[i][j]);
                int c = min(bestRec[i-1][j-1].second + 1, col[i][j]);

                int area = r * c - CalcUsed(i-c+1, j-r+1, i, j);
                int area1 = lin[i][j] - CalcUsed(i, j - lin[i][j] - 1, i, j);

                if(area1 > area)
                {
                    area = area1;
                    r = lin[i][j];
                    c = 1;
                }

                int area2 = col[i][j] - CalcUsed(i - col[i][j] - 1, j, i, j);

                if(area2 > area)
                {
                    area = area2;
                    r = 1;
                    c = col[i][j];
                }

                bestRec[i][j] = make_pair(r, c);

                if(area > maxArea)
                {
                    maxArea = area;
                    pos = make_pair(i, j);
                }
            }
        }

    pair<int, int> rec = bestRec[pos.first][pos.second];

    for(int i = pos.first - rec.second + 1; i <= pos.first; i++)
        for(int j = pos.second - rec.first + 1; j <= pos.second; j++)
            m[i][j] = 2;

    return maxArea;
}

void Solve()
{
    int firstArea = FindMaxRecArea();
    int secondArea = FindMaxRecArea();

    cout << firstArea + secondArea;
}

int main()
{
    SetInput("bmatrix");
    ReadInput();
    Solve();

    return 0;
}