Pagini recente » Cod sursa (job #910023) | Cod sursa (job #2796949) | Cod sursa (job #2203080) | Cod sursa (job #3233426) | Cod sursa (job #3313453)
#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;
}