插头DP模板

/*
插头dp模板
抄的GNAQ 的
括号表示法*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 13
#define mmp make_pair
using namespace std;
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
const int hs = 299987;
int mp[M][M], ex, ey, now, last, bit[30], g[2][300010], tot[2], n, m;
ll ans, f[2][300010];struct Note {
int nxt, to;
} note[300010];
int head[300010], cnt = 0;char s[M];void insert(int x, ll v) {
int key = x % hs;
for(int i = head[key]; i; i = note[i].nxt) {
if(g[now][note[i].to] == x) {
f[now][note[i].to] += v;
return;
}
}
tot[now]++;
g[now][tot[now]] = x;
f[now][tot[now]] = v;note[++cnt].nxt = head[key];
head[key] = cnt;
note[cnt].to = tot[now];
}void Dp() {
now = 1, last = 0;
tot[now] = 1;
f[now][1] = 1;
g[now][1] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= tot[now]; j++) g[now][j] <<= 2;
for(int j = 1; j <= m; j++) {
cnt = 0;
memset(head, 0, sizeof(head));
swap(now, last);
tot[now] = 0;
ll nowans;
int nowsta, sd, sr;
for(int k = 1; k <= tot[last]; k++) {
nowsta = g[last][k], nowans = f[last][k];
sd = (nowsta >> bit[j]) % 4, sr = (nowsta >> bit[j - 1]) % 4;
if(!mp[i][j]) {
if(!sd && !sr) insert(nowsta, nowans);
} else if(!sd && !sr) {
if(mp[i + 1][j] && mp[i][j + 1]) insert(nowsta + (1 << bit[j - 1]) + 2 * (1 << bit[j]), nowans);
} else if(!sd && sr) {
if(mp[i + 1][j]) insert(nowsta, nowans);
if(mp[i][j + 1]) insert(nowsta - sr * (1 << bit[j - 1]) + sr * (1 << bit[j]), nowans);
} else if(sd && !sr) {
if(mp[i + 1][j]) insert(nowsta - sd * (1 << bit[j]) + sd * (1 << bit[j - 1]), nowans);
if(mp[i][j + 1]) insert(nowsta, nowans);
} else if(sd == 1 && sr == 1) {
int count = 1;
for(int l = j + 1; l <= m; l++) {
if((nowsta >> bit[l]) % 4 == 1) count++;
else if((nowsta >> bit[l]) % 4 == 2) count--;
if(!count) {
insert(nowsta - (1 << bit[l]) - (1 << bit[j]) - (1 << bit[j - 1]), nowans);
break;
}
}
} else if(sd == 2 && sr == 2) {
int count = 1;
for(int l = j - 2; l >= 0; l--) {
if((nowsta >> bit[l]) % 4 == 1) count--;
else if((nowsta >> bit[l]) % 4 == 2) count++;
if(!count) {
insert(nowsta - 2 * (1 << bit[j]) - 2 * (1 << bit[j - 1]) + (1 << bit[l]), nowans);
break;
}
}
} else if(sd == 1 && sr == 2) {
insert(nowsta - 2 * (1 << bit[j - 1]) - (1 << bit[j]), nowans);
} else if(sd == 2 && sr == 1) {
if(i == ex && j == ey) ans += nowans;
}
}
}
}
}int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for(int j = 1; j <= m; j++) {
if(s[j] == '.') mp[i][j] = 1, ex = i, ey = j;
}
}
for(int i = 1; i <= 25; i++) bit[i] = i << 1;
Dp();
cout << ans << '\n';
return 0;
}