BOJ 27559 - Following Directions

BOJ 27559 - Following Directions

구현중 오타가 나서 고생했다.

$in[y][x]$ 를 자신에게 도달하는 소의 개수라고 하자.

그럼 각 쿼리마다 이 $in$ 배열을 업데이트 시켜준 후 모든 row와 column에 대해 vat 값과 in 의 개수를 곱해줘서 모두 더해준 것이 정답이고 이걸 세는건 $O(n)$에 된다.

그럼 $in$을 어떻게 업데이트 하냐가 문제의 핵심인데, $(y,x)$가 flip 되었을 때 $(y+1,x)$와 $(y,x+1)$ 의 $in$이 변한다.

이후에 $(y+1,x),(y,x+1)$ 로부터 끝까지 갈때까지 거치는 칸들에 대해서만 $in$이 변한다는 것을 증명할 수 있기 때문에 결국 업데이트도 $O(n)$으로 가능하다.

즉, $O(qn)$에 문제를 해결할 수 있다.

void solve() {
   int n;
   cin >> n;
   vs dir(n);
   vi cost_col(n + 5), cost_row(n + 5);
   for (int i = 0; i < n + 1; i++) {
      if (i < n) {
         cin >> dir[i];
         cin >> cost_row[i];
      } else {
         for (int j = 0; j < n; j++) cin >> cost_col[j];
      }
   }

   vvi in(n + 1, vi(n + 1));
   for (int y = 0; y < n; y++)
      for (int x = 0; x < n; x++) {
         in[y][x]++;
         if (dir[y][x] == 'D') in[y + 1][x] += in[y][x];
         else in[y][x + 1] += in[y][x];
      }
   ll ans = 0;
   for (int i = 0; i < n; i++) {
      ans += in[i][n] * cost_row[i];
      ans += in[n][i] * cost_col[i];
   }
   cout << ans << endl;

   int query;
   cin >> query;
   vvi vis(n + 1, vi(n + 1));
   while (query--) {
      int sy, sx;
      cin >> sy >> sx, sy--, sx--;
      dir[sy][sx] = dir[sy][sx] == 'D' ? 'R' : 'D';

      function<void(int, int)> fn = [&](int y, int x) -> void {
         in[y][x] = (y == n || x == n) ? 0 : 1;
         if (y != 0 && x != n && dir[y - 1][x] == 'D') in[y][x] += in[y - 1][x];
         if (x != 0 && y != n && dir[y][x - 1] == 'R') in[y][x] += in[y][x - 1];

         if (y == n || x == n) return;
         if (dir[y][x] == 'R') {
            fn(y, x + 1);
         } else {
            fn(y + 1, x);
         }
      };

      fn(sy + 1, sx);
      fn(sy, sx + 1);

      ans = 0;
      for (int i = 0; i < n; i++) {
         ans += in[i][n] * cost_row[i];
         ans += in[n][i] * cost_col[i];
      }
      //cout << "\n----------\n";
      //print(dir);
      //print(in);
      cout << ans << endl;
   }
}