【题目大意】
给出一个m*n的矩阵里面有一些格子为障碍物，求经过所有非障碍格子的哈密顿回路个数。
【思路】
最典型的插头DP。分为三种情况：
（1）当前格子既没有上插头也没有左插头。
如果下边和右边都没有障碍，新建连同分量。
（2）如果只有左插头或者右插头。
延伸或者拐弯，当然也要判断有没有障碍。
（3）上插头和左插头都没有。
1. 如果两个插头不连通（编号不一样），那么将两个插头所处的连通分量合并，标记相同的连通块标号，O(n)扫描保证最小表示；
2. 如果已经连通，相当于出现了一个回路，这种情况只能出现在最后一个非障碍格子。
由于状态非常多，用hash表存储状态。
decode和encode注意一下，这里不赘述了。
【错误点】
注意一下ch要开得够大，具体见代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int MAXN=;
const int HASH=;
int ex,ey;
int m,n;
int maze[MAXN][MAXN];
int code[MAXN],ch[MAXN];
struct HashMap
{
vector<int> hash[HASH];//存储f和state的下标
vector<ll> f,state;//存储对应的方案数和状态
void init()
{
for (int i=;i<HASH;i++) vector<int>().swap(hash[i]);
vector<ll>().swap(f);
vector<ll>().swap(state);
}
void push(ll st,ll ans)
{
int h=st%HASH;
for (int i=;i<hash[h].size();i++)
{
int now=hash[h][i];
if (state[now]==st)//如果已经存储了当前状态，直接累加
{
f[now]+=ans;
return;
}
}
//如果没有存储过当前状态，累加
state.push_back(st);
f.push_back(ans);
hash[h].push_back(state.size()-);
}
}dp[]; void decode(ll st)
{
memset(code,,sizeof(code));
for (int i=n;i>=;i--)
{
code[i]=st&;//每三位代表一个信息
st>>=;
}
} ll encode()
//用最小表示法重新编码
{
int cnt=;
memset(ch,-,sizeof(ch));
ch[]=;
long long st=;
for (int i=;i<=n;i++)
{
if (ch[code[i]]==-) ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=;
st|=code[i];
}
return st;
} void shift()
{
for (int i=n;i>;i--) code[i]=code[i-];
code[]=;
} void dpblank(int i,int j,int cur)
{
for (int k=;k<dp[-cur].state.size();k++)
{
decode(dp[-cur].state[k]);
int left=code[j-];//左插头
int up=code[j];//上插头 /*如果上下插头都没有*/
if (!left && !up)
{
if (maze[i][j+] && maze[i+][j])
{
code[j-]=code[j]=MAXN-;
//这里只要随便设置一个大数即可 //【attention】这里千万不可以设置成MAXN，否则ch数组会抱★★★★★★★★ //因为encode会重新用最小表示法编码
dp[cur].push(encode(),dp[-cur].f[k]);
}
} /*只有上插头或者只有左插头*/
if ((left&&(!up))||((!left)&&up))
{ int t=left|up;
if (maze[i][j+])//右边没有障碍
{
code[j-]=;
code[j]=t;
dp[cur].push(encode(),dp[-cur].f[k]);
}
if (maze[i+][j])//下面没有障碍
{
code[j-]=t;
code[j]=;
if (j==n) shift();
dp[cur].push(encode(),dp[-cur].f[k]);
}
} /*上插头和右插头都有*/
if (left && up)
{
if (left==up)
{
if (i==ex && j==ey)
{
code[j-]=code[j]=;
if (j==n) shift();
dp[cur].push(encode(),dp[-cur].f[k]);
}
}
else
{
code[j-]=code[j]=;
for (int t=;t<=n;t++)
if (code[t]==up) code[t]=left;
if (j==n) shift();
dp[cur].push(encode(),dp[-cur].f[k]);
}
}
}
} void dpblock(int i,int j,int cur)
{
int k=;
for (int k=;k<dp[-cur].state.size();k++)
{
decode(dp[-cur].state[k]);
code[j-]=code[j]=;
if (j==n) shift();
dp[cur].push(encode(),dp[-cur].f[k]);
}
} void solve()
{
int cur=;
ll ans=;
dp[cur].init();
dp[cur].push(,);//DP数组初始化
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)
{
cur^=;
dp[cur].init();
if (maze[i][j]) dpblank(i,j,cur);
else dpblock(i,j,cur); }
for (int i=;i<dp[cur].state.size();i++)
ans+=dp[cur].f[i];
printf("%lld",ans);
} void init()
{
memset(maze,,sizeof(maze));
ex=ey=;
for (int i=;i<=m;i++)
{
char str[MAXN];
scanf("%s",str);
for (int j=;j<n;j++)
{
if (str[j]=='.')
{
ex=i;
ey=j+;
maze[i][j+]=;
}
}
}
} int main()
{
while (scanf("%d%d",&m,&n)!=EOF)
{
init();
if (ex==) puts("");//如果没有一个是空格的话直接输出0
else solve();
}
return ;
}