SHARE
TWEET

Untitled

a guest Jul 17th, 2019 189 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Naman Bhalla on 2019-07-15.
  3. //
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. //char mat[19][19];
  9. int dp[19][1 << 19][2];
  10.  
  11. int main(){
  12.     ios_base::sync_with_stdio(0);
  13.     cin.tie(NULL);
  14.     cout.tie(NULL);
  15.  
  16.     int t;
  17.     cin >> t;
  18.  
  19.     for(int x = 0; x < t; ++x){
  20. //        memset(mat, 0, sizeof mat);
  21.         memset(dp, 0, sizeof dp);
  22.  
  23.         int n;
  24.  
  25.         cin >> n;
  26.         vector< string > mat(n + 1);
  27.  
  28.         for(int i = 1; i <= n; ++i){
  29.             cin >> mat[i];
  30.             mat[i].insert(0, "a");
  31. //            for(int j = 1; j <= n; ++j){
  32. //                cin >> mat[i][j];
  33. //            }
  34.         }
  35.  
  36.         for(int i = 1; i <= n; ++i){
  37.             for(int j = 0; j < (1 << (n + 1)); ++j){
  38.                 for(int l = 0; l < 2; ++l){
  39.                     dp[i][j][l] = dp[i - 1][j][l];
  40.                     if(j & (1 << i)){
  41.                         if(l == 1){
  42.                             if(mat[i][i] == 'C'){
  43.                                 dp[i][j][l] = max(dp[i][j][l], 1 + dp[i - 1][j ^ (1 << i)][l ^ 1]);
  44.                             }
  45.                         }
  46.                         for(int k = 1; k < i; ++k){
  47.                             if(mat[i][k] == 'C' and (j & (1 << k))){
  48.                                 dp[i][j][l] = max(dp[i][j][l], 1 + dp[i - 1][((j ^ (1 << i)) ^ (1 << k))][l]);
  49.                             }
  50.                         }
  51.                     }
  52. //                    cout << dp[i][j] << " ";
  53.                 }
  54.             }
  55. //            cout << endl;
  56.         }
  57.  
  58.  
  59.         if(n % 2)
  60.             cout << max(dp[n][((1 << (n + 1)) - 1) ^ 1][0], dp[n][((1 << (n + 1)) - 1) ^ 1][1]) << endl;
  61.         else
  62.             cout << dp[n][((1 << (n + 1)) - 1) ^ 1][0] << endl;
  63.  
  64.  
  65.     }
  66.  
  67.     return 0;
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top