Advertisement
Josif_tepe

Untitled

Apr 27th, 2022
660
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None
  1. #include <fstream>
  2. #include <iostream>
  3. using namespace std;
  4. int n, m;
  5. int mat[6][6];
  6. int one[6][6];
  7. int cnt;
  8. short dp[4][5][1 << 20];
  9. short rec(int i, int j, int bitmask, int skok) {
  10.     if(__builtin_popcount(bitmask) == cnt) {
  11.         return 1;
  12.     }
  13.     if(dp[i][j][bitmask] != -1) {
  14.         return dp[i][j][bitmask];
  15.     }
  16.     short result = 0;
  17.     if(skok == 0) {
  18.         for(int k = 0; k < n; k++) {
  19.             if(k != i and !(bitmask & (1 << one[k][j])) and mat[k][j] == 1) {
  20.                 int new_mask = (bitmask | (1 << one[k][j]));
  21.                 result = max(result, rec(k, j, new_mask, 1));
  22.             }
  23.         }
  24.     }
  25.     else {
  26.         for(int k = 0; k < m; k++) {
  27.             if(k != j and !(bitmask & (1 << one[i][k])) and mat[i][k] == 1) {
  28.                 int new_mask = (bitmask | (1 << one[i][k]));
  29.                 result = max(result, rec(i, k, new_mask, 0));
  30.             }
  31.         }
  32.     }
  33.     return dp[i][j][bitmask] = result;
  34. }
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(0);
  38.     cin >> n >> m;
  39.     cnt = 0;
  40.     for(int i = 0; i < n; i++) {
  41.         for(int j = 0; j < m; j++) {
  42.             cin >> mat[i][j];
  43.             if(mat[i][j] == 1) {
  44.                 one[i][j] = cnt;
  45.                 cnt++;
  46.             }
  47.         }
  48.     }
  49.     memset(dp, -1, sizeof dp);
  50.    
  51.     for(int i = 0; i < n; i++) {
  52.         for(int j = 0; j < m; j++) {
  53.             if(mat[i][j] == 1) {
  54.                 if(rec(i, j, (1 << one[i][j]), 1) == true) {
  55.                     cout << "DA" << endl;
  56.                     return 0;
  57.                 }
  58.             }
  59.         }
  60.     }
  61.     cout << "NE" << endl;
  62.     return 0;
  63. }
  64.  
Advertisement
RAW Paste Data Copied
Advertisement