插头DP基础题的样子。。。输入N,M<=11，以及N*M的01矩阵，0（1）表示有（无）障碍物。输出哈密顿回路（可以多回路）方案数。。。
看了个ppt，画了下图。。。感觉还是挺有效的。。。
参考http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.html
以及推荐cd琦的论文ppthttp://wenku.baidu.com/view/4fe4ac659b6648d7c1c74633.html
向中学生学习~~
感觉以后可能还会要看这篇日志。所以特意加了较多的注释。。。观客可以看注释=。=推荐画示意图。。。。
复杂度O（n*m*2^（m+1））
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-8 int a[][];
ll dp[][][<<];
int main(){
int t,ca=;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)for(int j=;j<=m;++j)scanf("%d",&a[i][j]);
memset(dp,,sizeof(dp));
dp[][][]=;
int ma=(<<(m+));
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
for(int k=;k<ma;++k){
int d=<<(j-),r=<<j;
if(a[i][j]){// 该位置无障碍
if( ( (k&d)&&(k&r) ) || ( (~k&d)&&(~k&r)) )// 右插下插同时有或同时无，必须翻转
dp[i][j][k]=dp[i][j-][k^d^r];
else // 右插下插只有一个，可翻转可不翻转
dp[i][j][k]=dp[i][j-][k]+dp[i][j-][k^d^r];
}
else {// 该位置有障碍
if((k&d)==&&(k&r)==)// 没有右插没有下插，则方案数跟随
dp[i][j][k]=dp[i][j-][k];
}
}
}
if(i+<=)
for(int k=;k<(<<m);++k)// 换行去掉上一行的右插,下一行的开头没有进来的左插，请画图
dp[i+][][k<<]=dp[i][m][k];
}
printf("Case %d: There are %I64d ways to eat the trees.\n",++ca,dp[n][m][]);
}
return ;
}
做了上面那个入门级别的插头DP。。。做了个还是入门级别的。。。。
输入N,M<=12，以及N*M的01矩阵，'*'（'.'）表示有（无）障碍物。输出哈密顿单回路方案数。。。
这一题需要用到括号匹配，最小表示法（上面那题可以不用，我的代码就是没有用到的）。。。
这一题参考了别人的代码，尝试了2种表示方法，一种是直接存括号对应的连通分量标号，一种是只存括号的类型。。。
我的第一种方法300+ms，第二种100+ms。。。感觉还是有点区别的。。。因为存连通分量标号需要用到3位（连通分量标号最大值为MAXM/2），而括号类型只需要2位
。。
而这题跟上一题的区别，就是，单哈密顿回路的括号匹配，如果左插是'('，下插是')'，那只能在最后一个非障碍物的位置连接。。。。
具体看代码吧。。。还是建议画下示意图。。。
还有一点就是，由于用到HASH，所以HASH太大太小都可能会TLE
300+ms的版本（其实就是那个链接里的。。。。）：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-8 #define maxd 15
#define HASH 100007
#define STATE 1000010 int n,m;
int maze[maxd][maxd],code[maxd];
int ch[maxd];//最小表示法使用
int ex,ey;//最后一个非障碍格子的坐标
struct HASHMAP{
int head[HASH],nxt[STATE],sz;
ll state[STATE];
ll f[STATE];
void clear(){sz=;memset(head,-,sizeof(head));}
void push(ll st,ll ans){
int h=st%HASH;
for(int i=head[h];i!=-;i=nxt[i])
if(state[i]==st){
f[i]+=ans;
return;
}
state[sz]=st;
f[sz]=ans;
nxt[sz]=head[h];
head[h]=sz++;
}
}hm[];
void decode(int *code,int m,ll st){
for(int i=m;i>=;i--)code[i]=st&,st>>=;
}
ll encode(int *code,int m){//最小表示法
int cnt=;
memset(ch,-,sizeof(ch));
ch[]=;
ll st=;
for(int i=;i<=m;i++){
if(ch[code[i]]==-)ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=;
st|=code[i];
}
return st;
}
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){
for(int k=;k<hm[cur].sz;k++){
decode(code,m,hm[cur].state[k]);
int left=code[j-],up=code[j];
if(left&&up){
if(left==up){//只能出现在最后一个非障碍格子
if(i==ex&&j==ey){
code[j-]=code[j]=;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
else{//不在同一个连通分量则合并
code[j-]=code[j]=;
for(int t=;t<=m;t++)
if(code[t]==up)code[t]=left;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
else if(left || up){
int t = left + up;
if(maze[i][j+]){
code[j-]=;
code[j]=t;
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
if(maze[i+][j]){
code[j-]=t;
code[j]=;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
else{//无插头，则构造新的连通块
if(maze[i][j+]&&maze[i+][j]){
code[j-]=code[j]=;
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur){
for(int k=;k<hm[cur].sz;k++){
decode(code,m,hm[cur].state[k]);
code[j-]=code[j]=;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
char str[maxd];
void init(){
memset(maze,,sizeof(maze));
ex=;
for(int i=;i<=n;i++){
scanf("%s",str+);
for(int j=;j<=m;j++){
if(str[j]=='.'){// 无障碍
ex=i,ey=j;
maze[i][j]=;
}
}
}
}
void solve(){
int cur=;
ll ans=;
hm[].clear();
hm[].push(,);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
hm[cur^].clear();
if(maze[i][j])dpblank(i,j,cur);
else dpblock(i,j,cur);
cur^=;
}
for(int i=;i<hm[cur].sz;i++)
ans+=hm[cur].f[i];
printf("%I64d\n",ans);
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
if(ex==)puts("");// 没有空的格子
else solve();
}
return ;
}
100+ms的版本（改编自那个链接里的。。。。）：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std; #define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-8 #define maxd 15
#define HASH 100007
#define STATE 1000010 int n,m;
int maze[maxd][maxd],code[maxd];
int ch[maxd];//最小表示法使用
int ex,ey;//最后一个非障碍格子的坐标
struct HASHMAP{
int head[HASH],nxt[STATE],sz;
ll state[STATE];
ll f[STATE];
void clear(){sz=;memset(head,-,sizeof(head));}
void push(ll st,ll ans){
int h=st%HASH;
for(int i=head[h];i!=-;i=nxt[i])
if(state[i]==st){
f[i]+=ans;
return;
}
state[sz]=st;
f[sz]=ans;
nxt[sz]=head[h];
head[h]=sz++;
}
}hm[];
void decode(int *code,int m,ll st){
for(int i=;i<=m;++i)code[i]=st&,st>>=;
}
ll encode(int *code,int m){//最小表示法
ll st=;
for(int i=m;i>=;--i)
st=st<<|code[i];
return st;
}
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){
for(int k=;k<hm[cur].sz;k++){
decode(code,m,hm[cur].state[k]);
int left = code[j-],up = code[j];
if(left&&up){
if(left== && up==){// 只能出现在最后一个非障碍格子
if(i==ex&&j==ey){
code[j-]=code[j]=;
ll tmp = encode(code,m);
if(j==m)tmp<<=;
hm[cur^].push(tmp,hm[cur].f[k]);
}
}
else{//不在同一个连通分量则合并
if(left== && up==){// ...(...(...))... ==> ...(...)...##...
for(int jj=j-,cnt=;jj>=;--jj){
if(code[jj]==)++cnt;
else if(code[jj]==)--cnt;
if(cnt==){code[jj]=-code[jj];break;}
}
code[j-]=code[j]=;
}
else if(left== && up==){// ...((...)...)... ==> ...##...(...)...
for(int jj=j,cnt=;jj<=m;++jj){
if(code[jj]==)++cnt;
else if(code[jj]==)--cnt;
if(cnt==){code[jj]=-code[jj];break;}
}
code[j-]=code[j]=;
}
else if(left== && up==){// ...(...)(...)... ==> ...(...##...)...
code[j-]=code[j]=;
}
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
else if(left || up){
int t = left | up;
if(maze[i][j+]){
code[j-]=;
code[j]=t;
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
if(maze[i+][j]){
code[j-]=t;
code[j]=;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
else{//无插头，则构造新的连通块
if(maze[i][j+]&&maze[i+][j]){
code[j-]=,code[j]=;
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur){
for(int k=;k<hm[cur].sz;k++){
decode(code,m,hm[cur].state[k]);
code[j-]=code[j]=;
if(j==m)shift(code,m);
hm[cur^].push(encode(code,m),hm[cur].f[k]);
}
}
char str[maxd];
void init(){
memset(maze,,sizeof(maze));
ex=;
for(int i=;i<=n;i++){
scanf("%s",str+);
for(int j=;j<=m;j++){
if(str[j]=='.'){// 无障碍
ex=i,ey=j;
maze[i][j]=;
}
}
}
}
void solve(){
int cur=;
ll ans=;
hm[].clear();
hm[].push(,);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
hm[cur^].clear();
if(maze[i][j])dpblank(i,j,cur);
else dpblock(i,j,cur);
cur^=;
}
for(int i=;i<hm[cur].sz;i++)
ans+=hm[cur].f[i];
printf("%I64d\n",ans);
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
if(ex==)puts("");// 没有空的格子
else solve();
}
return ;
}