单回路问题

/*
大体懂了，可j,j+1,j',(j+1)'的关系没弄懂
*/
#include <iostream>
#include <cstring>

using namespace std;

using ll=long long;
int n,m,ex,ey,st[2][300010],tot[2],pre;
ll f[2][300010],ans;
/*
pre ：滚动数组当前位置（pre^1，下一个或即将要求的位置）
f[pre][i] : 状态为 i 的方案数
st[pre][i] : hash 内去完重的状态
tot[pre] : hash 内状态个数
ex,ey : 最后一个非障碍点 
*/
char s[15];
int bin[15],a[15][15];
struct hash_table {//手写 hash 
	int head[300010],nxt[300010];
	const int mod = 299989;
	void ins(int x,ll s) {
		int id = x % mod + 1;
		for (int i = head[id];i;i = nxt[i]) {//同样的值下面找 
			if (st[pre][i] == x) {
				f[pre][i] += s;
				return;
			}
		}
		nxt[++tot[pre]] = head[id];//没有就在表头插入 
		head[id] = tot[pre];
		st[pre][tot[pre]] = x, f[pre][tot[pre]] = s;
	}
	void clear() {
		memset(head,0,sizeof head);
		tot[pre] = 0;
	}
};
hash_table H;
int read() {
	int s = 0,f = 1;char ch = getchar();
	while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
	while (isdigit(ch)) s = s * 10 + ch - '0', ch = getchar();
	return s*f;
}

int main() {
	n = read(), m = read();
	for (int i = 1;i <= n;i ++ ) {
		scanf("%s",s+1);
		for (int j = 1;j <= m;j ++ ) {
			a[i][j] = (s[j] == '.');
			if (s[j] == '.') ex = i, ey = j;
		}
	}
	bin[0] = 1;
	for (int i = 1;i <= 12;i ++ ) bin[i] = bin[i-1] << 2;
	//三进制转化为四进制，方便换行处理
	tot[pre] = f[pre][1] = 1, st[pre][1] = 0;
	for (int i = 1;i <= n;i ++ ) {
		for (int j = 1;j <= tot[pre];j ++ ) st[pre][j] <<= 2;
		//注意，这里左移 2 位是处理这一行到下一行轮廓线的转变，可以自己画图先想一想 
		for (int j = 1;j <= m;j ++) {
			pre ^= 1;
			H.clear();//清空 
			for (int k = 1;k <= tot[pre^1];k ++ ) {
				int nst = st[pre^1][k],p1 = (nst >> ((j-1)*2)) % 4,p2 = (nst >> (j*2)) % 4;
				//p1、p2是右插头和下插头 
				ll s = f[pre^1][k];
				if (!a[i][j]) {//第一种 
					//是障碍物，那么不能存在插头
					if (!p1 && !p2) H.ins(nst,s);
				}
				else if (!p1 && !p2) {
					//没有插头，为了构成回路，那么必须要有两个插头
					if (a[i][j+1] && a[i+1][j]) H.ins(nst + 2*bin[j] + bin[j-1],s);
					//加入了一个右插头和下插头
				}
				else if (!p1 && p2) {
					if (a[i][j+1]) H.ins(nst,s);
					if (a[i+1][j]) H.ins(nst-bin[j]*p2+bin[j-1]*p2,s);
					//往直走没有改变状态，拐弯就减去这一位加上上一位，因为轮廓线变动导致下标变了 
				}
				else if (p1 && !p2) {
					if (a[i][j+1]) H.ins(nst-bin[j-1]*p1+bin[j]*p1,s);// 同理 
					if (a[i+1][j]) H.ins(nst,s);
				}
				else if (p1 == 1 && p2 == 1) {
					int rb = 1;
					for (int l = j+1;l <= m;l ++ ) {//往右扫找到单独的右括号 （为了构成回路，匹配）
						if ((nst >> (l * 2)) % 4 == 1) rb ++;
						if ((nst >> (l * 2)) % 4 == 2) rb --;
						if (!rb) {
							H.ins(nst - bin[j] - bin[j-1] - bin[l],s);
							break;
						}
					}
				}
				else if (p1 == 2 && p2 == 2) {
					int lb = 1;
					for (int l = j-2;l >= 0;l -- ) {//往左找找到单独的左括号 
						if ((nst >> (l * 2)) % 4 == 1) lb --;
						if ((nst >> (l * 2)) % 4 == 2) lb ++;
						if (!lb) {
							H.ins(nst - 2*bin[j] - 2*bin[j-1] + bin[l],s);
							break;
						}
					}
				}
				else if (p1 == 2 && p2 == 1) H.ins(nst-2*bin[j-1]-bin[j],s);//直接连 
				else if (i == ex && j == ey) ans += s;//如果是最后的非障碍点，统计答案 
			}
		}
	}
	
	cout << ans << '\n';
}