Advertisement
Josif_tepe

Untitled

Mar 14th, 2023
659
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char mat[22][22];
  4. short n;
  5. short dp[1 << 21];
  6. vector<int> masks;
  7.  
  8. int rec(int bitmask) {
  9.     if(__builtin_popcount(bitmask) == n ) {
  10.          
  11.         return 0;
  12.     }
  13.     if(dp[bitmask] != -1) {
  14.         return dp[bitmask];
  15.     }
  16.     int res = 2e9;
  17.     for(int i = 0; i < n; i++) {
  18.         if(bitmask & (1 << i)) continue;
  19.         res = min(res, rec(bitmask | (1 << i)) + __builtin_popcount(bitmask & masks[i]));
  20.     }
  21.     return dp[bitmask] = res;
  22. }
  23. int main() {
  24.     ios_base::sync_with_stdio(false);
  25.     cin >> n;
  26.     for(int i = 0; i < n; i++) {
  27.         for(int j = 0; j < n; j++) {
  28.             cin >> mat[i][j];
  29.         }
  30.         int num = 0, pow = n - 1;
  31.         for(int j = n - 1; j >= 0; j--) {
  32.             if(mat[i][j] == 'D') {
  33.                 num |= (1 << pow);
  34.             }
  35.             pow--;
  36.         }
  37.         masks.push_back(num);
  38.     }
  39.    
  40.     memset(dp, -1, sizeof dp);
  41.     cout << rec(0) << endl;
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement