BOJ 21822 - Acowdemia III

BOJ 21822 - Acowdemia III

그리디하게 항상 $G$를 모두 제거해줘야 한다.

그런데

GC
CG

같은 경우가 문제가 된다.

어떤 $C$와 $G$를 잇냐에 따라 최적이 아니게 될 수 있기 때문이다.

$G$를 가장 효율적으로 쓰는 방법은 $CGC$가 가로나 세로로 있다면 항상 그것과 이어주는 것이다.

그런 경우는 무조건 두 $C$가 중앙에 있는 $G$를 사용하지 않고는 이루어질 수 없기 때문이다.

저 경우만 모두 이어준 다음, 완전탐색하면 된다.

void solve() {
   int Y, X;
   cin >> Y >> X;
   vs b(Y);
   fv(b);
   auto c = [&](int y, int x) -> int {
      if (y < 0 || y >= Y || x < 0 || x >= X) return 0;
      return b[y][x] == 'C';
   };
   auto g = [&](int y, int x) -> int {
      if (y < 0 || y >= Y || x < 0 || x >= X) return 0;
      return b[y][x] == 'G';
   };
   auto idx = [&](int y, int x) {
      return y * X + x;
   };

   set<pi> vis;
   auto in = [&](int y1, int x1, int y2, int x2) {
      int i1 = idx(y1, x1);
      int i2 = idx(y2, x2);
      if (i1 > i2)swap(i1, i2);
      pi key = mp(i1, i2);
      if (hass(vis, key)) return 0;
      vis.insert(key);
      return 1;
   };
   int ans = 0;

   for (int y = 0; y < Y; y++)
      for (int x = 0; x < X; x++) {
         if (g(y, x)) {
            if (c(y - 1, x) && c(y + 1, x)) {
               assert(in(y - 1, x, y + 1, x));
               b[y][x] = '.';
            } else if (c(y, x - 1) && c(y, x + 1)) {
               assert(in(y, x - 1, y, x + 1));
               b[y][x] = '.';
            }
         }
      }

   const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1}, op[] = {2, 3, 0, 1};
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         if (g(y, x)) {
            for (int d = 0; d < 4; d++) {
               for (int d2 = 0; d2 < 4; d2++) {
                  if (d == d2) continue;
                  int ny = y + dy[d], nx = x + dx[d];
                  int ny2 = y + dy[d2], nx2 = x + dx[d2];
                  if (c(ny, nx) && c(ny2, nx2)) {
                     if (in(ny, nx, ny2, nx2)) {
                        b[y][x] = '.';
                        goto out;
                     }
                  }
               }
            }
         }
         out:;
      }
   }

   cout << sz(vis);
}