Advertisement
wym1111

Untitled

Jun 21st, 2024
477
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. using ll = long long;
  6. #define endl '\n'
  7.  
  8. const int M = 13;
  9. const int offset = 4;
  10. const int mask = 15;
  11. const int N = 1e5 + 10;
  12. const int Prime = 9973;
  13.  
  14. struct Hash {
  15.     int head[Prime], nxt[N], sz;
  16.     int state[N];
  17.     ll key[N];
  18.    
  19.     void clear () {
  20.         sz = 0;
  21.         memset(head, -1, sizeof head);
  22.     }
  23.    
  24.     void push (int s, ll val) {
  25.         int x = s % Prime;
  26.         for (int i = head[x]; ~i; i = nxt[i]) {
  27.             if (state[i] == s) {
  28.                 key[i] += val;
  29.                 return;
  30.             }
  31.         }
  32.         state[sz] = s;
  33.         key[sz] = val;
  34.         nxt[sz] = head[x];
  35.         head[x] = sz ++;
  36.     }
  37.    
  38.     void roll () {
  39.         for (int i = 0; i < sz; i ++) {
  40.             state[i] <<= offset;
  41.         }
  42.     }
  43. }h[2];
  44.  
  45. int n, m;
  46. int a[M];
  47.  
  48. int encode () {
  49.     int s = 0;
  50.     vector<int> b(m + 1, -1);
  51.     b[0] = 0;
  52.     int now = 0;
  53.     for (int i = m; i >= 0; i --) {
  54.         if (b[a[i]]== -1) b[a[i]] = ++ now;
  55.         s <<= offset;
  56.         s |= b[a[i]];
  57.     }
  58.     return s;
  59. }
  60. void decode (int s) {
  61.     for (int i = 0; i <= m; i ++) {
  62.         a[i] = s & mask;
  63.         s >>= offset;
  64.     }
  65. }
  66.  
  67. void push (int i, int pos, int dn, int rt, ll val) {
  68.     a[pos] = dn;
  69.     a[pos + 1] = rt;
  70.     h[i].push(encode(), val);
  71. }
  72.  
  73. string mp[M];
  74.  
  75. void solve() {
  76.     cin >> n >> m;
  77.     int tx = 0, ty = 0;
  78.     for (int i = 0; i < n; i ++) {
  79.         cin >> mp[i];
  80.         for (int j = 0; j < m; j ++) {
  81.             if (mp[i][j] == '.') {
  82.                 tx = i;
  83.                 ty = j;
  84.             }
  85.         }
  86.     }
  87.     h[1].clear();
  88.     h[1].push(0, 1);
  89.     for (int i = 0; i <= tx; i ++) {
  90.         for (int j = 0; j < m; j ++) {
  91.             int now = (i * m + j) & 1;
  92.             int lst = now ^ 1;
  93.             h[now].clear();
  94.             for (int ii = 0; ii < h[lst].sz; ii ++) {
  95.                 decode(h[lst].state[ii]);
  96.                 ll val = h[lst].key[ii];
  97.                 int lt = a[j], up = a[j + 1];
  98.                 if (mp[i][j] == '*') {
  99.                     if (!lt && !up) {
  100.                         push(now, j, 0, 0, val);
  101.                     }
  102.                 } else {
  103.                     if (lt && up) {
  104.                         if (lt == up) {
  105.                             if (i == tx && j == ty) {
  106.                                 push(now, j, 0, 0, val);
  107.                             }
  108.                         } else {
  109.                             for (int k = 0; k <= m; k ++) {
  110.                                 if (a[k] == lt) a[k] = up;
  111.                             }
  112.                             push(now, j, 0, 0, val);
  113.                         }
  114.                     } else {
  115.                         if (lt || up) {
  116.                             int t = lt | up;
  117.                             if (i != n - 1) push(now, j, t, 0, val);
  118.                             if (j != m - 1) push(now, j, 0, t, val);
  119.                         } else {
  120.                             if (i != n - 1 && j != m - 1) {
  121.                                 push(now, j, m, m, val);
  122.                             }
  123.                         }
  124.                     }
  125.                 }
  126.             }
  127.             if (i == tx && j == ty) break;
  128.         }
  129. //      cout << (((i + 1) * m - 1) & 1) << endl;
  130.         h[((i + 1) * m - 1) & 1].roll();
  131.     }
  132. //  cout << tx << ' ' << ty << endl;
  133.     int ans = h[(tx * m - m + ty - 1) & 1].key[0];
  134. //  cout << ans << endl;
  135. //  cout << h[(tx * m - m + ty - 1) & 1].sz << endl;
  136.     if (h[(tx * m - m + ty - 1) & 1].sz != 1) ans = 0;
  137.     cout << ans << endl;
  138. }
  139.  
  140.  
  141. signed main() {
  142.     ios::sync_with_stdio(false);
  143.     cin.tie(nullptr);
  144.     int _ = 1;
  145. //  cin >> _;
  146.     while(_--)
  147.         solve();
  148.     return 0;
  149. }
  150.  
  151. /*
  152.  
  153.  */
  154.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement