Advertisement
den4ik2003

Untitled

Mar 22nd, 2022
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::vector;
  5. const int mod = 1e9 + 7;
  6.  
  7. bool TownHungryCheck(int mask, int town) { // 0 когда не голодают
  8.   return ((mask >> town) & 1);
  9. }
  10. // 1 насылаем голод, 0 - не насылаем голод
  11. bool CheckPossible(vector<vector<char>>& towns, int mask, int column, int n) {
  12.   for (int town = 0; town < n; ++town) {
  13.     if (TownHungryCheck(mask, town) && towns[town][column] == '+') {
  14.       return false;
  15.     }
  16.     if (!TownHungryCheck(mask, town) && towns[town][column] == '-') {
  17.       return false;
  18.     }
  19.   }
  20.   return true;
  21. }
  22.  
  23. bool CheckNeighboringTowns(int mask1, int mask2, int n) {
  24.   for (int town = 0; town < n - 1; ++town) {
  25.     if (TownHungryCheck(mask1, town) + TownHungryCheck(mask1, town + 1) +
  26.         TownHungryCheck(mask2, town) + TownHungryCheck(mask2, town + 1) != 2) {
  27.       return false;
  28.     }
  29.   }
  30.   return true;
  31. }
  32.  
  33. int main() {
  34.   int n, m;
  35.   std::cin >> n >> m;
  36.   vector<vector<char>> towns(n);
  37.   for (int i = 0; i < n; ++i) {
  38.     vector<char> temp_str_towns(m);
  39.     for (int j = 0; j < m; ++j) {
  40.       std::cin >> temp_str_towns[j];
  41.     }
  42.     towns[i] = temp_str_towns;
  43.   }
  44.   vector<vector<int>> hungry_answer_dp(m, vector<int>(1 << n));
  45.   for (int mask = 0; mask < (1 << n); ++mask) {
  46.     hungry_answer_dp[0][mask] = CheckPossible(towns, mask, 0, n);
  47.   }
  48.   for (int column = 0; column < m - 1; ++column) {
  49.     for (int mask = 0; mask < (1 << n); ++mask) {
  50.       int inverted_mask = ((1 << n) - 1) xor mask;
  51.       int copy_mask = mask;
  52.       if (CheckPossible(towns, inverted_mask, column + 1, n) and
  53.           CheckNeighboringTowns(inverted_mask, mask, n)) {
  54.         hungry_answer_dp[column + 1][inverted_mask] += hungry_answer_dp[column][mask];
  55.         hungry_answer_dp[column + 1][inverted_mask] %= mod;
  56.       }
  57.       if (CheckPossible(towns, copy_mask, column + 1, n) and
  58.           CheckNeighboringTowns(copy_mask, mask, n)) {
  59.         hungry_answer_dp[column + 1][copy_mask] += hungry_answer_dp[column][mask];
  60.         hungry_answer_dp[column + 1][copy_mask] %= mod;
  61.       }
  62.     }
  63.   }
  64.   int answer = 0;
  65.   for (int mask = 0; mask < (1 << n); ++mask) {
  66.     answer += CheckPossible(towns, mask, m - 1, n) * hungry_answer_dp[m - 1][mask];
  67.     answer %= mod;
  68.   }
  69.   std::cout << answer << std::endl;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement