Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::vector;
- const int mod = 1e9 + 7;
- bool TownHungryCheck(int mask, int town) { // 0 когда не голодают
- return ((mask >> town) & 1);
- }
- // 1 насылаем голод, 0 - не насылаем голод
- bool CheckPossible(vector<vector<char>>& towns, int mask, int column, int n) {
- for (int town = 0; town < n; ++town) {
- if (TownHungryCheck(mask, town) && towns[town][column] == '+') {
- return false;
- }
- if (!TownHungryCheck(mask, town) && towns[town][column] == '-') {
- return false;
- }
- }
- return true;
- }
- bool CheckNeighboringTowns(int mask1, int mask2, int n) {
- for (int town = 0; town < n - 1; ++town) {
- if (TownHungryCheck(mask1, town) + TownHungryCheck(mask1, town + 1) +
- TownHungryCheck(mask2, town) + TownHungryCheck(mask2, town + 1) != 2) {
- return false;
- }
- }
- return true;
- }
- int main() {
- int n, m;
- std::cin >> n >> m;
- vector<vector<char>> towns(n);
- for (int i = 0; i < n; ++i) {
- vector<char> temp_str_towns(m);
- for (int j = 0; j < m; ++j) {
- std::cin >> temp_str_towns[j];
- }
- towns[i] = temp_str_towns;
- }
- vector<vector<int>> hungry_answer_dp(m, vector<int>(1 << n));
- for (int mask = 0; mask < (1 << n); ++mask) {
- hungry_answer_dp[0][mask] = CheckPossible(towns, mask, 0, n);
- }
- for (int column = 0; column < m - 1; ++column) {
- for (int mask = 0; mask < (1 << n); ++mask) {
- int inverted_mask = ((1 << n) - 1) xor mask;
- int copy_mask = mask;
- if (CheckPossible(towns, inverted_mask, column + 1, n) and
- CheckNeighboringTowns(inverted_mask, mask, n)) {
- hungry_answer_dp[column + 1][inverted_mask] += hungry_answer_dp[column][mask];
- hungry_answer_dp[column + 1][inverted_mask] %= mod;
- }
- if (CheckPossible(towns, copy_mask, column + 1, n) and
- CheckNeighboringTowns(copy_mask, mask, n)) {
- hungry_answer_dp[column + 1][copy_mask] += hungry_answer_dp[column][mask];
- hungry_answer_dp[column + 1][copy_mask] %= mod;
- }
- }
- }
- int answer = 0;
- for (int mask = 0; mask < (1 << n); ++mask) {
- answer += CheckPossible(towns, mask, m - 1, n) * hungry_answer_dp[m - 1][mask];
- answer %= mod;
- }
- std::cout << answer << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement