先%%学长优秀博客：%%
并借用他的定义：
插头DP主要用来处理一系列基于连通性状态压缩的动态规划问题，处理的具体问题有很多种，并且一般数据规模较小。
由于棋盘有很特殊的结构，使得它可以与“连通性”有很强的联系，因此插头DP最常见的应用要数在棋盘模型上的应用了。
直接上题
一、HDU1693 Eat the Trees
题目大意：给出一张n*m有障碍的棋盘，要求用任意条回路遍历整个棋盘，不能经过障碍格子，要求统计不同的行走方案数。
Sample Input
2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1
Sample Output
Case 1: There are 3 ways to eat the trees.
Case 2: There are 2 ways to eat the trees.
具体过程请参考学长博客，我就不搬了（没素质），上解释代码
重点看Execution函数的分情况讨论的实现 （Execution中判断x==n，y==m的状况可以不写正常转移）
1 ^:不同则1,相同则0 2 &:全1则1,有0则0 3 #include <cstdio> 4 #include<iostream> 5 #include <cstring> 6 using namespace std; 7 typedef long long LL; 8 int n,m,bin[20],mp[13][13]; 9 LL f[13][13][(1<<12)+10];//f[i][j][k]表示转移完第i行第j列插头状态为k时的方案数 10 inline void Execution(int x,int y) 11 { 12 int plug1=bin[y-1],plug2=bin[y];//分类bin[y-1]为左插头，bin[y]为上插头 13 if(x==n&&y==m)//最后状态只走0即可 14 { 15 if(mp[x][y])//!障碍且j状态没有插头，^后为有两个插头，及由y-1有两个插头转移 16 f[x][y][0]+=f[x][y-1][plug1^plug2]; 17 else//障碍并且转移后保证没有插头及一定合法 18 f[x][y][0]=f[x][y-1][0];//所以没有插头连向它才合法转移 19 return; 20 } 21 for(int j=0;j<bin[m+1];j++)//枚举状态（此时第m+1个插头可以为1） 22 if(mp[x][y])//!障碍 23 { 24 f[x][y][j]+=f[x][y-1][j^plug1^plug2]; 25 //plug1^plug2的第y-1，y这两位为1（从0开始） 26 //如果j状态有两个插头，^后为没有插头，及由y-1的没有插头转移 27 //如果j状态没有插头，^后为有两个插头，及由y-1有两个插头转移 28 //如果j状态有一个，^10变01，及由y-1有一个插头且不转向转移来 29 //10变10没法实现，只能排除00/11的情况，直接变 30 if(((j>>(y-1))&1)==((j>>(y))&1)) continue;//都为没插头或都有 31 f[x][y][j]+=f[x][y-1][j];//10变10，及由y-1有一个插头转向转移 32 } 33 else//障碍 34 { 35 if(!(j&plug1)&&!(j&plug2))//y-1处理完后该格没有左插头和上插头，同((!((j>>(y-1))&1))&&(!((j>>y)&1))) 36 f[x][y][j]=f[x][y-1][j];//及没有插头连向它才合法转移 37 else f[x][y][j]=0;//否则方案数为0 38 } 39 } 40 int main() 41 { 42 int t; 43 scanf("%d",&t); 44 bin[0]=1; 45 for(int i=1;i<=15;i++) //2^最大方案数 46 bin[i]=bin[i-1]<<1; 47 //cout<<bin[8]<<endl; 48 for(int u=1;u<=t;u++) 49 { 50 scanf("%d%d",&n,&m); 51 for(int i=1;i<=n;i++) 52 for(int j=1;j<=m;j++) 53 scanf("%d",&mp[i][j]); 54 memset(f,0,sizeof(f)); 55 f[1][0][0]=1;//*************初始化第0格*****************// 56 for(int i=1;i<=n;i++) 57 { 58 for(int j=1;j<=m;j++) Execution(i,j);//逐格递推 59 if(i!=n)//行间转移:当前行的0到m-1转移到下一行的1到m 60 for(int j=0;j<bin[m];j++)//bin[m]及第m个插头不可能为1 61 f[i+1][0][j<<1]=f[i][m][j];//初始化第0格 62 } 63 printf("Case %d: There are %lld ways to eat the trees.\n",u,f[n][m][0]);//最后状态不能再有插头 64 } 65 }
注意点：（自己的zz错误）
（1）行间转移没判 i!=n 59行
（2）插头从0到m，第m个插头不能为1，写成bin[m+1] 60行
（3）行间转移j<<1写成j>>1，左移1后i+1行的第0位为0 61行
（4）判断都有或没有插头跳过时没&1 30行