SorahISA

GCJ18R2D

May 7th, 2021
636
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("Ofast", "unroll-loops")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define double long double
  7. using pii = pair<int, int>;
  8. template<typename T>
  9. using Prior = std::priority_queue<T>;
  10. template<typename T>
  11. using prior = std::priority_queue<T, vector<T>, greater<T>>;
  12.  
  13. #define X first
  14. #define Y second
  15. #define eb emplace_back
  16. #define ALL(x) begin(x), end(x)
  17. #define RALL(x) rbegin(x), rend(x)
  18. #define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
  19.  
  20. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. inline int getRand(int L, int R) {
  23.     if (L > R) swap(L, R);
  24.     return (int)(rng() % (uint64_t)(R - L + 1) + L);
  25. }
  26.  
  27. template<typename T1, typename T2>
  28. ostream& operator << (ostream &os, pair<T1, T2> p) {
  29.     os << "(" << p.first << "," << p.second << ")";
  30.     return os;
  31. }
  32.  
  33. template<typename T>
  34. ostream& operator << (ostream &os, vector<T> vec) {
  35.     for (int i = 0; i < vec.size(); ++i) {
  36.         if (i) os << " ";
  37.         os << vec[i];
  38.     }
  39.     return os;
  40. }
  41.  
  42. const int maxn = 20 + 1;
  43.  
  44. bitset<maxn> state[maxn];
  45. int p[maxn*maxn], sz[maxn*maxn];
  46.  
  47. int Find(int x) {return x ^ p[x] ? p[x] = Find(p[x]) : x;}
  48.  
  49. void Union(int r1, int c1, int r2, int c2) {
  50.     int p1 = Find(r1*maxn + c1), p2 = Find(r2*maxn + c2);
  51.     if (p1 == p2) return;
  52.     if (sz[p1] > sz[p2]) swap(p1, p2);
  53.     sz[p2] += sz[p1], p[p1] = p2;
  54. }
  55.  
  56. void solve() {
  57.     int R, C; cin >> R >> C;
  58.    
  59.     vector<string> A(R, string(C, ' '));
  60.     for (auto &str : A) cin >> str;
  61.    
  62.     int ans = 1;
  63.     for (int cutR = 0; cutR <= R; ++cutR) {
  64.         for (int cutC = 0; cutC <= C; ++cutC) {
  65.             for (int tp = 0; tp < (1<<4); ++tp) {
  66.                 for (int i = 0; i < maxn; ++i) state[i].reset();
  67.                 fill(sz, sz + maxn*maxn, 1), iota(p, p + maxn*maxn, 0);
  68.                
  69.                 for (int i = 0; i < R; ++i) {
  70.                     for (int j = 0; j < C; ++j) {
  71.                         if (i >= cutR and j >= cutC) state[i][j] = A[i][j] == "BW"[tp >> 0 & 1];
  72.                         if (i >= cutR and j <  cutC) state[i][j] = A[i][j] == "BW"[tp >> 1 & 1];
  73.                         if (i <  cutR and j >= cutC) state[i][j] = A[i][j] == "BW"[tp >> 2 & 1];
  74.                         if (i <  cutR and j <  cutC) state[i][j] = A[i][j] == "BW"[tp >> 3 & 1];
  75.                     }
  76.                 }
  77.                
  78.                 // if (cutR == 0 and cutC == 0 and tp == 0) {
  79.                     // cout << "=== TEST ===\n";
  80.                     // for (int i = 0; i < R; ++i) {
  81.                         // for (int j = 0; j < C; ++j) cout << state[i][j];
  82.                         // cout << "\n";
  83.                     // }
  84.                 // }
  85.                
  86.                 for (int i = 0; i < R; ++i) {
  87.                     for (int j = 0; j < C-1; ++j) {
  88.                         if (state[i][j] & state[i][j+1]) Union(i, j, i, j+1);
  89.                     }
  90.                 }
  91.                 for (int i = 0; i < R-1; ++i) {
  92.                     for (int j = 0; j < C; ++j) {
  93.                         if (state[i][j] & state[i+1][j]) Union(i, j, i+1, j);
  94.                     }
  95.                 }
  96.                
  97.                 ans = max(ans, *max_element(sz, sz + maxn*maxn));
  98.             }
  99.         }
  100.     }
  101.     cout << ans << "\n";
  102. }
  103.  
  104. int32_t main() {
  105.     fastIO();
  106.    
  107.     int t = 1; cin >> t;
  108.     for (int _ = 1; _ <= t; ++_) {
  109.         cout << "Case #" << _ << ": ";
  110.         solve();
  111.     }
  112.    
  113.     return 0;
  114. }
RAW Paste Data