BOJ 25713 - 괴도 인하

BOJ 25713 - 괴도 인하

항상 $\to$나 $\downarrow$로 이동하므로 어떤 직사각형에 진입할 수 있는 경우는 저 두 가지이다.

그러므로 각 직사각형마다 제일 위 행과 제일 왼쪽 열만 각각의 경우에 대해 imos법으로 구간합을 구해두자.

그런다음 dp를 돌려주면 된다.

void solve() {
   struct stat st;
   fstat(0, &st);
   char *p = (char *) mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
   auto readInt = [&]() {
      int ret = 0;
      for (char c = *p++; c & 16; ret = 10 * ret + (c & 15), c = *p++);
      return ret;
   };
   int Y = readInt(), X = readInt(), K = readInt();
   cin >> Y >> X >> K;
   vector<array<int, 4>> C(K);

   vvi psum_t(Y + 1, vi(X + 1));
   auto psum_r = psum_t;

   for (auto &[y1, x1, y2, x2]: C) {
      y1 = readInt() - 1, x1 = readInt() - 1, y2 = readInt() - 1, x2 = readInt() - 1;
      if (y1 > y2) swap(y1, y2);
      if (x1 > x2) swap(x1, x2);

      psum_t[y1][x1]++;
      psum_t[y1][x2 + 1]--;
      psum_t[y1 + 1][x1]--;
      psum_t[y1 + 1][x2 + 1]++;
      psum_r[y1][x1]++;
      psum_r[y1][x1 + 1]--;
      psum_r[y2 + 1][x1]--;
      psum_r[y2 + 1][x1 + 1]++;
   }

   for (int y = 0; y < Y; y++)
      for (int x = 1; x < X; x++) {
         psum_t[y][x] += psum_t[y][x - 1];
         psum_r[y][x] += psum_r[y][x - 1];
      }
   for (int y = 1; y < Y; y++)
      for (int x = 0; x < X; x++) {
         psum_t[y][x] += psum_t[y - 1][x];
         psum_r[y][x] += psum_r[y - 1][x];
      }

   vvi dp(Y, vi(X, 1e9));
   dp[0][0] = psum_t[0][0];
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         if (y == 0 && x == 0) continue;

         if (y) {
            dp[y][x] = min(dp[y][x], dp[y - 1][x] + psum_t[y][x]);
         }
         if (x) {
            dp[y][x] = min(dp[y][x], dp[y][x - 1] + psum_r[y][x]);
         }
      }
   }
   cout << dp[Y - 1][X - 1];

}