题目大意：
给定一个图，一部分点'*'作为障碍物，求经过所有非障碍点的汉密尔顿回路有多少条
基础的插头DP题目，对于陈丹琦的论文来说我觉得http://blog.sina.com.cn/s/blog_51cea4040100gmky.html
这个博客写的更容易理解，不过好像这篇博客里的代码有问题，反正是A不了题目的
不过上面的图和思路写的很清楚，可以作为参考
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
#define ll unsigned long long
const int HASH_SIZE = ; bool mp[][];
char str[][];
int n, m , k , nn , mm;
int tot[] , bit[] , hash[HASH_SIZE] , state[][HASH_SIZE];
ll dp[][HASH_SIZE] , ans; void init()
{
//每一位用4进制保存,那么对于每一个状态来说都是右移2次，所以这里i*2
for(int i= ; i<= ; i++) bit[i] = i<<;
memset(dp , , sizeof(dp));
tot[] = dp[][] = , ans = k = ;
state[][] = ;
} void hash_in(int s , ll sum)//s表示当前状态，sum是指s状态下共有sum种方式形成
{
// print(s);
// cout<<" "<<sum<<endl;
int p = s%HASH_SIZE;
while(hash[p]){
if(state[k][hash[p]] == s){
dp[k][hash[p]] += sum;
return ;
}
p++;
if(p == HASH_SIZE) p=;
}
hash[p] = ++tot[k];
state[k][hash[p]] = s;
dp[k][hash[p]] = sum;
} void work()
{
for(int i= ; i<=n ; i++){
for(int j= ; j<=m ; j++){
k^= ; //滚动数组
tot[k] = ;
memset(hash , , sizeof(hash));
for(int u= ; u<=tot[-k] ; u++){
int s = state[-k][u] , curs;
ll sum = dp[-k][u];
int p = (s>>bit[j-])& , q = (s>>bit[j])&; //3进制 , 用( , # , )来理解
if(!mp[i][j]){
if(p== && q==) hash_in(s , sum);
}
else{
if(p == && q == ){
if(!mp[i+][j] || !mp[i][j+]) continue;
curs = s + (<<bit[j-]) + (<<bit[j]);
hash_in(curs , sum);
}
else if(!p && q){
if(mp[i][j+]) hash_in(s , sum);
if(mp[i+][j]){
curs = s+q*(<<bit[j-])-q*(<<bit[j]);
hash_in(curs , sum);
}
}
else if(p && !q){
if(mp[i+][j]) hash_in(s , sum);
if(mp[i][j+]){
curs = s - p*(<<bit[j-])+p*(<<bit[j]);
hash_in(curs , sum);
}
}
else if(p+q==){ //可理解为p==1 && q==1
int cnt = ;
for(int v=j+ ; v<=m ; v++){
int w = (s>>bit[v])&;
if(w == ) cnt++;
if(w == ) cnt--;
if(!cnt){
curs = s-(<<bit[v]); //将)转化为( ->状态由2->1 , 减少了一个
break;
}
}
curs = curs-(<<bit[j])-(<<bit[j-]);
hash_in(curs , sum);
}
else if(p+q==){//可理解为p==2 && q==2
int cnt = ;
for(int v=j- ; v>= ; v--){
int w = (s>>bit[v])&;
if(w == ) cnt--;
if(w == ) cnt++;
if(!cnt){
curs= s+(<<bit[v]);
break;
}
}
curs = curs-(<<bit[j])-(<<bit[j-]);
hash_in(curs , sum);
}
else if(p== && q==){
if(i==nn && j==mm)
ans+=sum;
}
else if(p== && q==){
curs = s-(<<bit[j-])-(<<bit[j]);
hash_in(curs , sum);
}
}
}
}
for(int j= ; j<=tot[k] ; j++) state[k][j]<<=;
}
printf("%lld\n" , ans);
} int main()
{
// freopen("in.txt" , "r" , stdin);
while(~scanf("%d%d" , &n , &m))
{
memset(mp , , sizeof(mp));
for(int i= ; i<=n ; i++){
scanf("%s" , str[i]+);
for(int j= ; j<=m ; j++){
mp[i][j] = str[i][j]=='.';
// if(mp[i][j]) cout<<i<<" "<<j<<endl;
if(mp[i][j]) nn=i , mm=j;//记录最后一个可执行块
}
}
init();
work();
}
return ;
}
后来写hdu上的题目的时候觉得kuangbin的表达方式还是很清晰的，所以又将源代码修改成了：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
#define ll unsigned long long
const int HASH = ;
const int STATE = ;
const int MAXD = ;
int n , m , enx , eny;
int code[MAXD] , mp[MAXD][MAXD];
ll ans = ; struct HASHMAP{
int head[HASH] , next[STATE] , state[STATE] , size;
ll f[STATE]; void init(){
size = ;
memset(head , - , sizeof(head));
} void push_in(int st , ll sum){
int h = st%HASH;
for(int i = head[h] ; ~i ; i=next[i]){
if(st == state[i]){
f[i]+=sum;
return ;
}
}
f[size]=sum;
state[size] = st;
next[size] = head[h];
head[h] = size++;
}
}hashmap[]; void decode(int *code , int m , int st)
{
for(int i=m ; i>= ; i--){
code[i] = st&;
st>>=;
}
} int encode(int *code , int m)
{
int st=;
for(int i= ; i<=m ; i++){
st<<=;
st |= code[i];
}
return st;
} void init()
{
char str[MAXD][MAXD];
for(int i= ; i<=n ; i++){
scanf("%s" , str[i]+);
for(int j= ; j<=m ; j++){
if(str[i][j] == '.'){
mp[i][j] = ;
enx = i , eny = j;
}else mp[i][j] = ;
}
mp[i][m+]=;
mp[n+][i] = ;
}
} void shift(int *code , int m) //换行,可理解为将最右侧轮廓线换到了下一行的最左侧
{
for(int i=m ; i>= ; i--) code[i] = code[i-];
code[] = ;
} void dpblank(int i , int j , int cur) //处理可执行格子
{
// cout<<"ok: "<<i<<" "<<j<<endl;
int k , left , up;
for(k= ; k<hashmap[cur].size ; k++){
decode(code , m , hashmap[cur].state[k]);
left = code[j-];
up = code[j];
if(!left && !up){
if(!mp[i][j+] || !mp[i+][j]) continue;
code[j-] = , code[j] = ;
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
else if(!left && up){
if(mp[i][j+]) hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
if(mp[i+][j]){
code[j-] = up , code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else if(left && !up){
if(mp[i+][j]){
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
if(mp[i][j+]){
code[j-] = , code[j] = left;
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else if(left== && up == ){
int cnt = ;
for(int v=j+ ; v<=m ; v++){
if(code[v]==)cnt++;
if(code[v]==)cnt--;
if(!cnt){
code[v]=;
break;
}
}
code[j-] = code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
else if(left == && up == ){
int cnt=;
for(int v=j- ; v>= ; v--){
if(code[v]==)cnt++;
if(code[v]==)cnt--;
if(!cnt){
code[v]=;
break;
}
}
code[j-] = code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
else if(left== && up==){
if(i==enx && j==eny) ans+=hashmap[cur].f[k];
}
else{
code[j-]=code[j]=;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
} void dpblock(int i , int j , int cur)
{
// cout<<"flase: "<<i<<" "<<j<<endl;
int k , left , up;
for(k= ; k<hashmap[cur].size ; k++){
decode(code , m , hashmap[cur].state[k]);
left = code[j-] , up = code[j];
if(!left && !up){
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
} ll solve()
{
ans = ;
int cur = ;
hashmap[cur].init();
hashmap[cur].push_in( , );
for(int i= ; i<=n ; i++){
for(int j= ; j<=m ; j++){
hashmap[cur^].init();
if(mp[i][j]) dpblank(i , j , cur);
else dpblock(i , j , cur);
cur ^= ;
}
}
return ans;
} int main()
{
// freopen("in.txt" , "r" , stdin);
while(~scanf("%d%d" , &n , &m))
{
init();
printf("%I64d\n" , solve());
}
return ;
}