niyaznigmatullin

Untitled

Apr 19th, 2014
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <cstdio>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1000000007;
  7.  
  8. void add(int & a, int b) {
  9.   a += b;
  10.   if (a >= MOD) a -= MOD;
  11. }
  12.  
  13. int a[123][123];
  14.  
  15. int main() {
  16.   map<long long, int> ways;
  17.   int n, m;
  18.   scanf("%d%d", &n, &m);
  19.   for (int i = 0; i < n; i++) {
  20.     for (int j = 0; j < m; j++) {
  21.       int c = getchar();
  22.       while (c <= 32) c = getchar();
  23.       a[i][j] = c;
  24.     }
  25.   }
  26.   ways[0] = 1;
  27.   for (int col = 0; col < m; col++) {
  28.     for (int row = 0; row < n; row++) {
  29.       map<long long, int> nways;
  30.       for (map<long long, int> :: iterator it = ways.begin(); it != ways.end(); ++it) {
  31.         long long state = it->first;
  32.         for (int c = 1; c <= 3; c++) {
  33.           if (a[row][col] != '.' && a[row][col] != "BGW"[c - 1]) continue;
  34.           if (row > 0 && ((state >> (2 * (row - 1))) & 3) == c) continue;
  35.           int cc = ((state >> (2 * row)) & 3);
  36.           if (cc == c) continue;
  37.           long long nState = state ^ ((cc ^ c) << (2 * row));
  38.           add(nways[nState], it->second);
  39.         }
  40.       }
  41.       ways.swap(nways);
  42.     }
  43.   }
  44.   int ans = 0;
  45.   for (map<long long, int> :: iterator it = ways.begin(); it != ways.end(); ++it) {
  46.     add(ans, it->second);
  47.   }
  48.   printf("%d\n", ans);
  49. }
Advertisement
Add Comment
Please, Sign In to add comment