Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- using ll = long long;
- #define endl '\n'
- const int M = 13;
- const int offset = 4;
- const int mask = 15;
- const int N = 1e5 + 10;
- const int Prime = 9973;
- struct Hash {
- int head[Prime], nxt[N], sz;
- int state[N];
- ll key[N];
- void clear () {
- sz = 0;
- memset(head, -1, sizeof head);
- }
- void push (int s, ll val) {
- int x = s % Prime;
- for (int i = head[x]; ~i; i = nxt[i]) {
- if (state[i] == s) {
- key[i] += val;
- return;
- }
- }
- state[sz] = s;
- key[sz] = val;
- nxt[sz] = head[x];
- head[x] = sz ++;
- }
- void roll () {
- for (int i = 0; i < sz; i ++) {
- state[i] <<= offset;
- }
- }
- }h[2];
- int n, m;
- int a[M];
- int encode () {
- int s = 0;
- vector<int> b(m + 1, -1);
- b[0] = 0;
- int now = 0;
- for (int i = m; i >= 0; i --) {
- if (b[a[i]]== -1) b[a[i]] = ++ now;
- s <<= offset;
- s |= b[a[i]];
- }
- return s;
- }
- void decode (int s) {
- for (int i = 0; i <= m; i ++) {
- a[i] = s & mask;
- s >>= offset;
- }
- }
- void push (int i, int pos, int dn, int rt, ll val) {
- a[pos] = dn;
- a[pos + 1] = rt;
- h[i].push(encode(), val);
- }
- string mp[M];
- void solve() {
- cin >> n >> m;
- int tx = 0, ty = 0;
- for (int i = 0; i < n; i ++) {
- cin >> mp[i];
- for (int j = 0; j < m; j ++) {
- if (mp[i][j] == '.') {
- tx = i;
- ty = j;
- }
- }
- }
- h[1].clear();
- h[1].push(0, 1);
- for (int i = 0; i <= tx; i ++) {
- for (int j = 0; j < m; j ++) {
- int now = (i * m + j) & 1;
- int lst = now ^ 1;
- h[now].clear();
- for (int ii = 0; ii < h[lst].sz; ii ++) {
- decode(h[lst].state[ii]);
- ll val = h[lst].key[ii];
- int lt = a[j], up = a[j + 1];
- if (mp[i][j] == '*') {
- if (!lt && !up) {
- push(now, j, 0, 0, val);
- }
- } else {
- if (lt && up) {
- if (lt == up) {
- if (i == tx && j == ty) {
- push(now, j, 0, 0, val);
- }
- } else {
- for (int k = 0; k <= m; k ++) {
- if (a[k] == lt) a[k] = up;
- }
- push(now, j, 0, 0, val);
- }
- } else {
- if (lt || up) {
- int t = lt | up;
- if (i != n - 1) push(now, j, t, 0, val);
- if (j != m - 1) push(now, j, 0, t, val);
- } else {
- if (i != n - 1 && j != m - 1) {
- push(now, j, m, m, val);
- }
- }
- }
- }
- }
- if (i == tx && j == ty) break;
- }
- // cout << (((i + 1) * m - 1) & 1) << endl;
- h[((i + 1) * m - 1) & 1].roll();
- }
- // cout << tx << ' ' << ty << endl;
- int ans = h[(tx * m - m + ty - 1) & 1].key[0];
- // cout << ans << endl;
- // cout << h[(tx * m - m + ty - 1) & 1].sz << endl;
- if (h[(tx * m - m + ty - 1) & 1].sz != 1) ans = 0;
- cout << ans << endl;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int _ = 1;
- // cin >> _;
- while(_--)
- solve();
- return 0;
- }
- /*
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement