这是一道最经典的基于连通性的状态压缩dp。f[i][j][s]表示轮廓线到i，j格的时候，轮廓线上状态为s的方案数。
用一个四进制数表示s：
0表示该位置没有插头，1表示该位置的插头必须拐弯，2表示这个插头不必须被延长，3表示该插头必须被延长。
具体转移请见程序：
#include<iostream>#include<cstring>#include<cstdio>using namespace std;typedef long long LLint;const LLint MAXN=110;const LLint HASHSIZE=3000009;const LLint MOD=20110520;LLint n,m;char Cmd[MAXN][MAXN];int Map[MAXN][MAXN];LLint t[MAXN];LLint Hash[HASHSIZE];LLint State[2][HASHSIZE][2];int Now,Bef,Lx,Ly;LLint Total[2],Tot,Ans;void Push(LLint Pos,LLint Cnt){ int h=Pos%HASHSIZE; while(Hash[h]){ if(State[Now][Hash[h]][0]==Pos){ State[Now][Hash[h]][1]=(State[Now][Hash[h]][1]+Cnt)%MOD; return ; } ++h; if(h>=HASHSIZE) h=0; } Total[Now]++; Hash[h]=Total[Now]; State[Now][Hash[h]][0]=Pos; State[Now][Hash[h]][1]=Cnt%MOD;}int main(){ //freopen("floor10.in","r",stdin); scanf("%I64d%I64d",&n,&m); for(int i=1;i<=n;++i) scanf("%s",&Cmd[i][1]); if(n<m){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ if(Cmd[i][j]=='_'){ Map[j][n-i+1]=1; } else Map[j][n-i+1]=0; } swap(n,m); } else{ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ if(Cmd[i][j]=='_'){ Map[i][j]=1; Lx=i; Ly=j; } else Map[i][j]=0; } } for(int i=1;i<MAXN;++i) t[i]=i<<1; State[Now][1][1]=1; Total[Now]++; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(Map[i][j]){ Lx=i; Ly=j; } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ Now^=1; Bef=Now^1; memset(Hash,0,sizeof(Hash)); Tot=Total[Bef]; Total[Bef]=Total[Now]=0; for(int k=1;k<=Tot;++k){ LLint Pos=State[Bef][k][0]; LLint Cnt=State[Bef][k][1]; int Up=(Pos>>t[j])%4; int Lt=(Pos>>t[j-1])%4; State[Bef][k][0]=State[Bef][k][1]=0; if(!Map[i][j]){ if(!Up&&!Lt){ Push(Pos,Cnt); } continue; } if(!Up&&!Lt){ if(Map[i+1][j]){ int Next=Pos^(1<<t[j-1]); Push(Next,Cnt); } if(Map[i][j+1]){ int Next=Pos^(1<<t[j]); Push(Next,Cnt); } if(Map[i+1][j]&&Map[i][j+1]){ int Next=Pos^(3*(1<<t[j-1]))^(3*(1<<t[j])); Push(Next,Cnt); } continue; } if(Up&&!Lt){ if(Up==1){ if(Map[i+1][j]){ int Next=Pos^(1<<t[j-1])^(1<<t[j]); Push(Next,Cnt); } if(Map[i][j+1]){ int Next=Pos^(1<<t[j])^((1<<t[j])*3); Push(Next,Cnt); } } if(Up==2){ if(Map[i+1][j]){ int Next=Pos^((1<<t[j-1])<<1)^((1<<t[j])<<1); Push(Next,Cnt); } if(Map[i][j]){ int Next=Pos^((1<<t[j])<<1); Push(Next,Cnt); } if(Lx==i&&Ly==j) Ans=(Ans+Cnt)%MOD; } if(Up==3){ if(Map[i+1][j]){ int Next=Pos^((1<<t[j])*Up)^((1<<t[j-1])<<1); Push(Next,Cnt); } if(Map[i][j]){ int Next=Pos^((1<<t[j])*Up); Push(Next,Cnt); } if(i==Lx&&j==Ly){ Ans=(Ans+Cnt)%MOD; } continue; } } if(!Up&&Lt){ if(Lt==1){ if(Map[i+1][j]){ int Next=Pos^((1<<t[j-1])*3)^(1<<t[j-1]); Push(Next,Cnt); } if(Map[i][j+1]){ int Next=Pos^(1<<t[j-1])^(1<<t[j]); Push(Next,Cnt); } } if(Lt==2){ if(Map[i][j+1]){ int Next=Pos^((1<<t[j-1])<<1)^((1<<t[j])<<1); Push(Next,Cnt); } if(Map[i][j]){ int Next=Pos^((1<<t[j-1])<<1); Push(Next,Cnt); } if(Lx==i&&Ly==j) Ans=(Ans+Cnt)%MOD; } if(Lt==3){ if(Map[i][j+1]){ int Next=Pos^((1<<t[j-1])*3)^((1<<t[j])<<1); Push(Next,Cnt); } if(Map[i][j]){ int Next=Pos^((1<<t[j-1])*3); Push(Next,Cnt); } if(Lx==i&&Ly==j){ Ans=(Ans+Cnt)%MOD; } } continue; } if(Up==1&&Lt==1){ int Next=Pos^(1<<t[j])^(1<<t[j-1]); Push(Next,Cnt); if(Lx==i&&Ly==j) Ans=(Ans+Cnt)%MOD; } } } for(int j=1;j<=Total[Now];++j) State[Now][j][0]<<=2; } printf("%I64d",Ans);return 0;}
转载于:https://www.cnblogs.com/Return-0/archive/2013/04/18/3028642.html
相关资源：数据结构—成绩单生成器