Advertisement
Guest User

Untitled

a guest
Jan 19th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 33;
  6.  
  7. int n, m;
  8. long long dp[N][N][N];
  9. char grid[N][N];
  10.  
  11. bool ok(int x, int y, char c) {
  12.   if (c == '.') return true;
  13.   else if (c == 'B') {
  14.     for (int i = 0; i <= x; i++) {
  15.       for (int j = 0; j <= y; j++) {
  16.         if (grid[i][j] != '.' && grid[i][j] != c) return false;
  17.         grid[i][j] = c;
  18.       }
  19.     }
  20.   } else if (c == 'R') {
  21.     for (int i = x; i < n; i++) {
  22.       for (int j = y; j < m; j++) {
  23.         if (grid[i][j] != '.' && grid[i][j] != c) return false;
  24.         grid[i][j] = c;
  25.       }
  26.     }
  27.   } else assert(0);
  28.   return true;
  29. }
  30.  
  31. int main() {
  32.   scanf("%d %d", &n, &m);
  33.   for (int i = 0; i < n; i++) {
  34.     scanf("%s", grid[i]);
  35.   }
  36.   for (int i = 0; i < n; i++) {
  37.     for (int j = 0; j < m; j++) {
  38.       if (!ok(i, j, grid[i][j])) {
  39.         puts("0");
  40.         return 0;
  41.       }
  42.     }
  43.   }
  44.   for (int i = 0; i <= n; i++) {
  45.     for (int j = 0; j <= m; j++) {
  46.       dp[i][j][0] = 1;
  47.     }
  48.   }
  49.   for (int i = 0; i < n; i++) {
  50.     for (int j = m - 1; j >= 0; j--) {
  51.       if (grid[i][j] == '.') {
  52.         if (i > 0 && grid[i - 1][j] == '.') {
  53.           for (int k = 1; k <= max(n, m); k++) {
  54.             dp[i][j][0] += dp[i - 1][j][k];
  55.           }
  56.         }
  57.         if (i == 0 || (grid[i - 1][j] != 'R')) for (int k = 1; k <= max(n, m); k++) {
  58.           dp[i][j][k] += dp[i][j + 1][k - 1];
  59.         }
  60.       }
  61.     }
  62.   }
  63.   for (int i = 0; i < n; i++) {
  64.     for (int j = 0; j < m; j++) {
  65.       if (grid[i][j] == '.') {
  66.         for (int k = 0; k <= max(n, m); k++) {
  67.           if (i > 0) dp[i - 1][j][k] = 0;
  68.           dp[i][j + 1][k] = 0;
  69.         }
  70.       } else {
  71.         for (int k = 0; k <= max(n, m); k++) {
  72.           dp[i][j][k] = 0;
  73.         }
  74.       }
  75.     }
  76.   }
  77.   long long ans = 1;
  78.   for (int i = 0; i < n; i++) {
  79.     for (int j = 0; j < m; j++) {
  80.       long long sum = 0;
  81.       for (int k = 0; k <= max(n, m); k++) {
  82.         sum += dp[i][j][k];
  83.       }
  84.       if (sum > 0) ans *= sum;
  85.     }
  86.   }
  87.   printf("%lld\n", ans);
  88.   return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement