Advertisement
Josif_tepe

Untitled

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