Cod sursa(job #3328884)

Utilizator fumfummititelu david fumfum Data 10 decembrie 2025 22:23:27
Problema Puteri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <stack>
#include <utility>
#include <algorithm>
#define N 1245
using namespace std;

ifstream gg("ternar.in");
ofstream wp("ternar.out");

short int a[N][N], l[N][N], c[N][N];
int n, m, s;
int xs, xd, ys, yd;
short dx[] = {0, 1, 0, -1};
short dy[] = {1, 0, -1, 0};

inline bool interior(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void citire() {
    gg >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            gg >> a[i][j];
            if (a[i][j] == 1) {
                l[i][j] = l[i][j - 1] + 1;
                c[i][j] = c[i - 1][j] + 1;
            } else
                l[i][j] = c[i][j] = 0;
        }
}

void fill(short i, short j) {
    stack<pair<short, short>> st;
    st.push({i, j});
    a[i][j] = 0;
    s = 1;
    xs = xd = i;
    ys = yd = j;
    while (!st.empty()) {
        short x = st.top().first;
        short y = st.top().second;
        st.pop();
        xs = min(xs, (int)x);
        xd = max(xd, (int)x);
        ys = min(ys, (int)y);
        yd = max(yd, (int)y);
        for (int dir = 0; dir < 4; ++dir) {
            short nx = x + dx[dir];
            short ny = y + dy[dir];
            if (interior(nx, ny) && a[nx][ny] == 2) {
                a[nx][ny] = 0;
                ++s;
                st.push({nx, ny});
            }
        }
    }
}

void finish() {
    int ariemax = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j] == 2) {
                fill(i, j);
                int sl = xd - xs + 1;
                int sc = yd - ys + 1;
                if (s == sl * sc) {
                    int top = xs - 1;
                    int bottom = xd + 1;
                    int left = ys - 1;
                    int right = yd + 1;
                    if (top >= 1 && bottom <= n && left >= 1 && right <= m) {
                        if (l[top][right] >= sc + 2 && l[bottom][right] >= sc + 2 && c[bottom][right] >= sl + 2 &&
                            c[bottom][left] >= sl + 2)
                            ariemax = max(ariemax, (sl + 2) * (sc + 2));
                    }
                }
            }
    wp << ariemax;
}

int main() {
    citire();
    finish();
    return 0;
}