题意：给一个n*m的矩阵，格子中是'*'则是障碍格子，不允许进入，其他格子都是必走的格子，所走格子形成一条哈密顿回路，问有多少种走法？
思路：
本来是很基础的题，顿时不知道进入了哪个坑。这篇插头DP的文章够详细，推荐一看（最好不要照抄代码）。
细节要小心，比如输出用I64d，必须用long long，判断是否无哈密顿回路，位操作等等。
这次仍然用括号表示法，1表示(，2表示)。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
const int mod=;
const int NN=;
char g[N][N];
int cur, n, m, ex, ey;
struct Hash_Map
{
int head[mod]; //桶指针
int next[NN]; //记录链的信息
int status[NN]; //状态
LL value[NN]; //状态对应的DP值。
int size; void clear() //清除哈希表中的状态
{
memset(head, -, sizeof(head));
size = ;
} void insert(int st, LL val) //插入状态st的值为val
{
int h = st%mod;
for(int i=head[h]; i!=-; i=next[i])
if(status[i] == st) //这个状态已经存在，累加进去。
{
value[i] += val;
return ;
}
status[size]= st; //找不到状态st，则插入st。
value[size] = val;
next[size] = head[h] ; //新插入的元素在队头
head[h] = size++;
}
}hashmap[]; int getbit(int s,int pos) //取出状态s的第pos个插头
{
int bit=;
if(s&(<<(*pos+))) bit+=; //高位对应高位
if(s&(<<*pos)) bit+=;
return bit;
}
int setbit(int s,int pos,int bit) //将状态s的第pos个插头设置为bit
{
if(s&(<<*pos )) s^=<<(*pos);
if(s&(<<(*pos+))) s^=<<(*pos+);
return (s|(bit<<*pos));
} int Fr(int s,int pos,int bit) //寻找状态s的第pos个插头对应的右括号。
{
int cnt=;
for(pos+=; pos<m; pos++)
{
if(getbit(s, pos)==-bit) cnt++;
if(getbit(s, pos)==bit) cnt--;
if(cnt==-) return setbit(s, pos, -bit);
}
}
int Fl(int s,int pos,int bit) //寻找状态s的第pos个插头对应的左括号。
{
int cnt=;
for(pos--; pos>=; pos--)
{
if(getbit(s, pos)==-bit) cnt++;
if(getbit(s, pos)==bit) cnt--;
if( cnt==-) return setbit(s, pos, -bit);
}
} void DP(int i,int j) //非障碍空格
{
for(int k=,t; k<hashmap[cur^].size; k++)
{
int s=hashmap[cur^].status[k];
LL v=hashmap[cur^].value[k];
int R=getbit(s,j), D=getbit(s,j+);
if(g[i][j]=='*') //障碍格子
{
if( R== && D== ) hashmap[cur].insert(s, v);
continue ;
}
if(R && D) //两个括号
{
t=(setbit(s,j,)&setbit(s,j+,));
if(R==D) //同个方向的括号
{
if(R==) t=Fr(t, j, ); //要改
else t=Fl(t, j, );
hashmap[cur].insert(t, v);
}
if( R== && D== ) //不同的连通分量
hashmap[cur].insert(t, v);
if(i==ex && j==ey && R== && D== ) //终点时'('和')'才可以合并。
hashmap[cur].insert(t, v);
}
else if(R || D) //仅1个括号
{
hashmap[cur].insert(s,v);
if(R) t=setbit(setbit(s,j,),j+,R);
else t=setbit(setbit(s,j+,),j,D);
hashmap[cur].insert(t,v);
}
else //无括号
hashmap[cur].insert( setbit(s,j,)|setbit(s,j+,), v);
}
} void cal()
{
if(ex==-) return ; //无空格
for(int i=; i<n; i++)
{
cur^=;
hashmap[cur].clear();
for(int j=; j<hashmap[cur^].size; j++) //新行，需要左移一下状态。
if( getbit( hashmap[cur^].status[j], m)== ) //多余的状态需要去除
hashmap[cur].insert( hashmap[cur^].status[j]<<, hashmap[cur^].value[j] );
for(int j=; j<m; j++)
{
cur^=;
hashmap[cur].clear();
DP(i,j);
if(i==ex && j==ey) return ; //终点
}
}
} LL print()
{
for(int i=; i<hashmap[cur].size; i++) //寻找轮廓线状态为0的值。
if( hashmap[cur].status[i]== )
return hashmap[cur].value[i];
return ;
}
int main()
{
//freopen("input.txt", "r", stdin);
while(~scanf("%d%d",&n,&m))
{
ex=ey=-;
cur=;
for(int i=; i<n; i++) //输入矩阵
for(int j=; j<m; j++)
{
char c=getchar();
if(c=='.'||c=='*')
{
g[i][j]=c;
if( c=='.' ) ex=i,ey=j;//终点空格
}
else j--;
} hashmap[cur].clear();
hashmap[cur].insert(, ); //初始状态
cal();
cout<<print()<<endl;
}
return ;
}
AC代码