题目
求一个网格图的哈密顿回路个数。
分析
插头dp模板题。
学插头dp时的博客：浅谈插头dp
插头dp有两种判断连通性的办法，第一个是最小表示法，第二个是括号序。
这里使用后者。
同时，插头dp的状态是有重复的，并且还有很多非法的，这里我们通过哈希使得只存储了合法状态，这样会让插头dp变得很快，但是时间复杂度也变得不好分析。
回到这道题，这里需要讨论十多种情况，不再赘述，如果需要看的请移步上边的博客。
注意坑点（这个写法的）：因为这里偷懒了没有判断边界，所以初始的 (vis) 一定要设置好！
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
#define PII pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ull unsigned long long
const int N=3e5+5,M=20,INF=1e9+7,MOD=299993;
struct state{int a[M];};
int n,m,now,lst,edi,edj;
ll Ans,val[N<<1],to[N<<1];
int head[N],nex[N<<1],idx[2];
struct Node{int nex,to[2];ll val[2];}s[N];
inline void Insert(int x,ll v){
int key=x%MOD;
for(int i=head[key];i;i=s[i].nex) if(s[i].to[now]==x) return s[i].val[now]+=v,void();
s[++idx[now]].nex=head[key];
s[idx[now]].to[now]=x;
s[idx[now]].val[now]=v;
head[key]=idx[now];
return ;
}
inline state Unpack(ll x){
state S;S.a[0]=x&3;
for(ll i=1;i<=m;i++) S.a[i]=((x>>(i<<1))&3);
return S;
}
inline ll Judge(state S){
int res=0;res|=S.a[0];
for(ll i=1;i<=m;i++) res|=(S.a[i]<<(i<<1));
return res;
}
char str[M];
bool vis[M][M];
void DP(){
Insert(0,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
lst=now,now^=1;memset(head,0,sizeof(head));idx[now]=0;
for(int k=1;k<=idx[lst];k++){
state tmp=Unpack(s[k].to[lst]),las=tmp;
ll num=s[k].val[lst];int west=las.a[0],north=las.a[j];
if(!vis[i][j]){
if(!west&&!north) Insert(Judge(las),num);
continue;
}
if(!west&&!north){
if(vis[i+1][j]&&vis[i][j+1]){
las.a[0]=2,las.a[j]=1;
Insert(Judge(las),num);
las=tmp;
}
continue;
}
if(!west&&north){
if(vis[i+1][j]) Insert(Judge(las),num);
if(vis[i][j+1]){
las.a[j]=0,las.a[0]=north;
Insert(Judge(las),num);
las=tmp;
}
continue;
}
if(west&&!north){
if(vis[i][j+1]) Insert(Judge(las),num);
if(vis[i+1][j]){
las.a[j]=west,las.a[0]=0;
Insert(Judge(las),num);
las=tmp;
}
continue;
}
if(west==1&&north==1){
int pos,res=1;
for(pos=j+1;pos<=m;pos++){
res+=las.a[pos]==1?1:las.a[pos]==2?-1:0;
if(res==0) break;
}
las.a[pos]=1,las.a[0]=las.a[j]=0;
Insert(Judge(las),num);las=tmp;
continue;
}
if(west==2&&north==2){
int pos,res=-1;
for(pos=j-1;pos;pos--){
res+=las.a[pos]==1?1:las.a[pos]==2?-1:0;
if(res==0) break;
}
las.a[pos]=2,las.a[0]=las.a[j]=0;
Insert(Judge(las),num);las=tmp;
continue;
}
if(west==2&&north==1){
las.a[0]=las.a[j]=0;
Insert(Judge(las),num);
las=tmp;
continue;
}
if(west==1&&north==2){
bool fl=0;
las.a[0]=las.a[j]=0;
for(int pos=0;pos<=m;pos++){if(las.a[pos]){fl=true;break;}}
if(!fl&&i==edi&&j==edj) Ans+=num;
continue;
}
}
}
}
return ;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++){
scanf("%s",str+1);
for(int j=1;j<=m;j++){
if(str[j]!='*') edi=i,edj=j,vis[i][j]=true;
else vis[i][j]=false;
}
}
DP();
write(Ans);
return 0;
}