BOJ 3050 - 집들이
구간합 배열을 전처리한다.
어떤 $(y,x)$에서 시작해서 오른쪽으로 쭉 가면서 최대로 넓힐 수 있는 $+y$ 방향으로의 세로 길이를 계속 좁혀가며 관리한다.
이렇게 $O(n^3)$ 으로 완전탐색하면 풀 수 있다.
void solve() {
int Y, X;
cin >> Y >> X;
vs b(Y);
fv(b);
vvi psum(Y + 1, vi(X + 1));
for (int y = 0; y < Y; y++)
for (int x = 0; x < X; x++)
psum[y + 1][x + 1] = (b[y][x] == 'X') + psum[y + 1][x] + psum[y][x + 1] - psum[y][x];
auto q = [&](int y1, int x1, int y2, int x2) {
return psum[y2 + 1][x2 + 1] - psum[y2 + 1][x1] - psum[y1][x2 + 1] + psum[y1][x1];
};
int ans = 0;
for (int sy = 0; sy < Y; sy++) {
for (int sx = 0; sx < X; sx++) {
if (b[sy][sx] == 'X') continue;
int ey = Y - 1;
for (int x = sx; x < X; x++) {
if (b[sy][x] == 'X') break;
while (q(sy, sx, ey, x)) ey--;
maxa(ans, (ey - sy + 1) * 2 + (x - sx + 1) * 2 - 1);
}
}
}
cout << ans;
}
Comments