Cod sursa(job #3313453)

Utilizator SGLDCASA SI PODUL SGLD Data 4 octombrie 2025 16:53:35
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("perimeter.in");
ofstream out("perimeter.out");
int N;
vector<string> grid;
vector<vector<bool>> visited;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
pair<int,int> dfs(int sr, int sc) {
    stack<pair<int,int>> st;
    st.push({sr, sc});
    visited[sr][sc] = true;
    int area = 0;
    int perimeter = 0;
    while (!st.empty()) {
        auto [r, c] = st.top();
        st.pop();
        area++;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                perimeter++;
            } else if (grid[nr][nc] == '.') {
                perimeter++;
            } else if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                st.push({nr, nc});
            }
        }
    }
    return {area, perimeter};
}

int main() {
    in >> N;
    grid.resize(N);
    for (int i = 0; i < N; i++) {
        in >> grid[i];
    }
    visited.assign(N, vector<bool>(N, false));
    int bestArea = 0;
    int bestPerimeter = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (grid[r][c] == '#' && !visited[r][c]) {
                auto [area, perim] = dfs(r, c);
                if (area > bestArea || (area == bestArea && perim < bestPerimeter)) {
                    bestArea = area;
                    bestPerimeter = perim;
                }
            }
        }
    }
    out << bestArea << " " << bestPerimeter <<endl;
    return 0;
}