轮廓线dpdpdp模板题。
题意简述：给一个放有障碍的网格图，问有多少种方法能使所有非障碍格子都在同一条哈密顿回路上面。
考虑用括号序列的写法来状压这个轮廓线。
用000表示没有插头，111表示有插头，且是左括号，222表示有插头，且是右括号。
然后分类讨论一波：
- 对于当前的格子左边，上边都有插头。
- 只有左边有插头。
- 只有上边有插头。
- 左边，上边都没有插头。
其中第一种还要分类讨论一波：
- 两个插头都是左括号。
- 两个插头都是右括号
- 左边的是左括号，右边的是右括号
- 左边的是右括号，右边的是左括号
然后注意细节转移即可，注意如果像我一样用四进制实现三进制的话要手写一波hashhashhash表。
代码：
#include<bits/stdc++.h>#include<tr1/unordered_map>#define ri register intusing namespace std;using namespace tr1;typedef long long ll;int n,m,zx=-1,zy=-1,cur;bool mp[15][15];char s[15];ll ans=0;const int mod=1e6+7;struct Statement{int tot,idx[mod],sta[mod];ll num[mod];inline void clear(){memset(idx,-1,sizeof(idx)),tot=0;}inline void insert(int stat,ll nume){int pos=stat%mod;if(!pos)++pos;while(~idx[pos]&&sta[idx[pos]]!=stat)pos=pos==mod-1?1:pos+1;if(~idx[pos])num[idx[pos]]+=nume;else sta[idx[pos]=++tot]=stat,num[tot]=nume;}}f[2];inline int getbit(int x,int p){return (x>>((p-1)<<1))&3;}inline void update(int&x,int p,int v){x^=((v&3)^getbit(x,p))<<((p-1)<<1);}inline void solve(){cur=0,f[cur].clear(),f[cur].insert(0,1);for(ri i=1;i<=n;++i){for(ri j=1;j<=m;++j){cur^=1,f[cur].clear();for(ri tt=1;tt<=f[cur^1].tot;++tt){int stat=f[cur^1].sta[tt],p=getbit(stat,j),q=getbit(stat,j+1);ll dpnum=f[cur^1].num[tt];if(!mp[i][j]){if(!(p+q))f[cur].insert(stat,dpnum);continue;}if(!(p+q)){if(mp[i][j+1]&&mp[i+1][j])update(stat,j,1),update(stat,j+1,2),f[cur].insert(stat,dpnum);continue;}if(!p){if(mp[i][j+1])f[cur].insert(stat,dpnum);if(mp[i+1][j])update(stat,j,q),update(stat,j+1,0),f[cur].insert(stat,dpnum);continue;}if(!q){if(mp[i+1][j])f[cur].insert(stat,dpnum);if(mp[i][j+1])update(stat,j,0),update(stat,j+1,p),f[cur].insert(stat,dpnum);continue;}if(p==1&&q==2){if(i==zx&&j==zy)ans+=dpnum;continue;}update(stat,j,0),update(stat,j+1,0);if(p==2&&q==1){f[cur].insert(stat,dpnum);continue;}if(p==1){int cnt=1;for(ri k=j+2;k<=m+1;++k){int bit=getbit(stat,k);if(bit==1)++cnt;if(bit==2)--cnt;if(!cnt){update(stat,k,1);break;}}f[cur].insert(stat,dpnum);continue;}int cnt=-1;for(ri k=j-1;k;--k){int bit=getbit(stat,k);if(bit==1)++cnt;if(bit==2)--cnt;if(!cnt){update(stat,k,2);break;}}f[cur].insert(stat,dpnum);}}for(ri j=1;j<=f[cur].tot;++j)f[cur].sta[j]<<=2;}}int main(){scanf("%d%d",&n,&m);for(ri i=1;i<=n;++i){scanf("%s",s+1);for(ri j=1;j<=m;++j){mp[i][j]=s[j]=='.';if(mp[i][j])zx=i,zy=j;}}if(zx==-1)return puts("-1"),0;solve();cout<<ans;return 0;}
