BOJ 3050 - 집들이

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;
}