插头DP
楼教主男人八题之一！
要求从左下角走到右下角的哈密顿路径数量。
啊嘞，我只会求哈密顿回路啊……这可怎么搞……
容易想到：要是把起点和重点直接连上就变成一条回路了……那么我们就连一下~
我们可以在整张图下面加两行：(例：3*5)
1 1 1 1 1
1 1 1 1 1
1 1 1
0 0 0
1 1 1 1 1
红色的是原来的起点和终点，下面紫色的路径将这两个点连了起来= =然后这题瞬间就变回了Formula 1那题……求哈密顿回路数量，so easy有没有~（其实不这样加也可以做，起点终点特判下就可以）
因为就变成原题了……我就试着默写了一次模板……结果好几个细节给挂了：
单插头的时候，两种状态转移都要判是否合法的= =！！！（sigh……做了一道HDU 1964直接就傻逼了……因为那题是没有障碍物的……）
两个插头都没有的时候的转移写错了……(┬＿┬)不可以乘p/q的……因为它俩都是0啊……
程序一开始的时候bit数组的初始化……
Source Code
Problem: User: sdfzyhy
Memory: 2668K Time: 125MS
Language: G++ Result: Accepted Source Code //POJ 1739
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e7+,INF=~0u>>;
const double eps=1e-;
typedef unsigned long long u64;
/*******************template********************/
const int M=;
bool mp[][];
int n,m,k;
int tot[],bit[],hash[M],state[][M];
u64 dp[][M],ans;
#define debug
void init(){
CC(mp,);
CC(dp,);
tot[]=dp[][]=,ans=k=;
state[][]=;
char ch;
F(i,,n){
scanf("%c",&ch);
F(j,,m){
scanf("%c",&ch);
mp[i][j]=ch=='.';
}
}
n+=;
F(j,,m) mp[n][j]=;
mp[n-][]=mp[n-][m]=;
}
void hash_in(int s,u64 sum){
int p=s%M;
while(hash[p]){
if (state[k][hash[p]]==s){
dp[k][hash[p]]+=sum;
return;
}
p++;
if (p==M) p=;
}
hash[p]=++tot[k];
state[k][hash[p]]=s;
dp[k][hash[p]]=sum;
}
#define in hash_in(s,sum)
void work(){
F(i,,n){
F(j,,m){
k^=;
CC(hash,);
tot[k]=;
F(u,,tot[-k]){
int s=state[-k][u];
u64 sum=dp[-k][u];
int p=(s>>bit[j-])&,q=(s>>bit[j])&;
if (!mp[i][j]){ if (!p && !q) in; }
else{
if (!p && !q){
if (!mp[i+][j] || !mp[i][j+]) continue;
s=s^(<<bit[j-])^(<<bit[j]<<),in;
}else if(!p && q){
if (mp[i][j+]) in;
if (mp[i+][j]) s=s^q*(<<bit[j])^q*(<<bit[j-]),in;
}else if(p && !q){
if (mp[i+][j]) in;
if (mp[i][j+]) s=s^p*(<<bit[j])^p*(<<bit[j-]),in;
}else if(p+q==){
int nd=;
F(u,j+,m){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd){ s-=<<bit[u]; break; }
}s=s^(<<bit[j-])^(<<bit[j]),in;
}else if(p+q==){
int nd=;
D(u,j-,){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd){ s+=<<bit[u]; break; }
}s=s^(<<bit[j-]<<)^(<<bit[j]<<),in;
}else if(p== && q==){
if (i==n && j==m) ans+=sum;
}else if(p== && q==) s=s^(<<bit[j-]<<)^(<<bit[j]),in;
}
}
}
F(j,,tot[k]) state[k][j]<<=;
}
printf("%llu\n",ans);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
F(i,,) bit[i]=i<<;
while(scanf("%d%d",&n,&m)!=EOF && n){
init();
work();
}
return ;
}