括号表示法：
据说比下一个要快而且灵活。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define LL long long 5 #define MAXN 20000 6 #define HASH 23333 7 #define ma(x,y) memset(x,y,sizeof(x)) 8 using namespace std; 9 struct Hash_map 10 { 11 int size,first[HASH],next[MAXN]; 12 #define f(x) first[x] 13 #define n(x) next[x] 14 LL sta[MAXN],sum[MAXN]; 15 void init(){size=0;ma(first,-1);ma(sum,0);} 16 void push(LL states,LL Sum) 17 { 18 int pos=(states%HASH+HASH)%HASH; 19 for(int i=f(pos);i>=0;i=n(i)) 20 if(sta[i]==states){sum[i]+=Sum;return;} 21 sta[size]=states; 22 sum[size]=Sum; 23 n(size)=f(pos);f(pos)=size++; 24 } 25 }dp[2]; 26 int n,m,map[15][15],bin[16],fx,fy;//最后一个可行点坐标 27 int now,pre; 28 int mov[13]={0,2,4,6,8,10,12,14,16,18,20,22,24}; 29 inline int getbit(LL st,int k){return (st>>mov[k])&3;}//第k位状态 30 inline int pybit(LL st,int k){return st<<mov[k];}//平移k位 31 inline LL clrbit(LL st,int i,int j){return st&(~(3<<mov[i]))&(~(3<<mov[j]));}//清空i，j位 32 inline int fl(LL st,int pos)//从左往右找和当前pos位置匹配的右括号 33 { 34 int cnt=1; 35 for(int i=pos+1;i<=m;i++) 36 { 37 int k=getbit(st,i); 38 if(k==1)cnt++; 39 else if(k==2)cnt--; 40 if(!cnt)return i; 41 } 42 } 43 inline int fr(LL st,int pos)//从右往左找和当前pos位置匹配的左括号 44 { 45 int cnt=1; 46 for(int i=pos-1;i>=0;i--) 47 { 48 int k=getbit(st,i); 49 if(k==1)cnt--; 50 else if(k==2)cnt++; 51 if(!cnt)return i; 52 } 53 } 54 void DP(int x,int y,int k) 55 { 56 int l=getbit(dp[pre].sta[k],y-1); 57 int up=getbit(dp[pre].sta[k],y); 58 LL st=clrbit(dp[pre].sta[k],y-1,y); 59 LL v=dp[pre].sum[k]; 60 if(!l&&!up) 61 { 62 if(!map[x][y]){dp[now].push(st,v);return;} 63 if(x<n&&y<m&&map[x+1][y]&&map[x][y+1]) 64 dp[now].push(st|pybit(1,y-1)|pybit(2,y),v); 65 } 66 else if(!l||!up) 67 { 68 int e=l+up; 69 if(x<n&&map[x+1][y]) 70 dp[now].push(st|pybit(e,y-1),v); 71 if(y<m&&map[x][y+1]) 72 dp[now].push(st|pybit(e,y),v); 73 } 74 else if(l==1&&up==1) 75 dp[now].push(st^pybit(3,fl(st,y)),v); 76 else if(l==2&&up==2) 77 dp[now].push(st^pybit(3,fr(st,y-1)),v); 78 else if(l==2&&up==1) 79 dp[now].push(st,v); 80 else if(x==fx&&y==fy) 81 dp[now].push(st,v); 82 } 83 LL solve() 84 { 85 dp[0].init(); 86 dp[0].push(0,1); 87 now=0,pre=1; 88 for(int i=1;i<=n;i++) 89 { 90 pre=now,now^=1;dp[now].init(); 91 for(int k=0;k<dp[pre].size;k++) 92 dp[now].push(pybit(dp[pre].sta[k],1),dp[pre].sum[k]); 93 for(int j=1;j<=m;j++) 94 { 95 pre=now,now^=1;dp[now].init(); 96 for(int k=0;k<dp[pre].size;k++) 97 DP(i,j,k); 98 } 99 } 100 for(int i=0;i<dp[now].size;i++) 101 if(dp[now].sta[i]==0) 102 return dp[now].sum[i]; 103 return 0; 104 } 105 signed main() 106 { 107 // freopen("in.txt","r",stdin); 108 109 bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]*2; 110 cin>>n>>m;char t; 111 for(int i=1;i<=n;i++) 112 for(int j=1;j<=m;j++) 113 { 114 cin>>t; 115 if(t=='*')map[i][j]=0; 116 else map[i][j]=1; 117 } 118 fx=0; 119 for(int i=n;i>0&&!fx;i--) 120 for(int j=m;j>0&&!fx;j--) 121 if(map[i][j]) 122 fx=i,fy=j; 123 if(fx==0)puts("0"); 124 else cout<<solve()<<endl; 125 }
最小表示法（看不懂，下面是标程）：
不过连我都能看出来它慢那它就是真的慢了。而且我也并没有觉得它好理解……
找到一个和自己码风相似的不容易啊……
1 #include<bits/stdc++.h> 2 3 #define LL long long 4 using namespace std; 5 const int maxn=30001,inc=3,bit=7;//3位二进制以及111的表示 6 int n,m,now,pre,code[20],bin[20],res[20];//用来表示状态的每一位的数值 7 char gp[20][20],fx,fy;//图和最后的可行点 8 struct node//离散化hash 9 { 10 int head[maxn],next[maxn],size; 11 LL sum[maxn],sta[maxn]; 12 void clear() 13 { 14 memset(head,-1,sizeof(head)); 15 size=0; 16 } 17 void push(LL st,const LL v) 18 { 19 LL hash=st%maxn; 20 for(int i=head[hash];i>=0;i=next[i]) 21 { 22 if(sta[i]==st) 23 { 24 sum[i]+=v; 25 return ; 26 } 27 } 28 sta[size]=st,sum[size]=v; 29 next[size]=head[hash],head[hash]=size++; 30 } 31 }dp[2]; 32 inline LL encode(int m)//将code转换成状态 33 { 34 LL st=0; 35 int cnt=1; 36 memset(bin,-1,sizeof(bin)); 37 bin[0]=0; 38 for(int i=m;i>=0;i--) 39 { 40 if(bin[code[i]]==-1) 41 bin[code[i]]=cnt++; 42 code[i]=bin[code[i]]; 43 st<<=inc; 44 st|=code[i]; 45 } 46 return st; 47 } 48 inline void decode(LL st,int m)//将状态转换成code 49 { 50 for(int i=0;i<=m;i++) 51 { 52 code[i]=st&bit; 53 st>>=inc; 54 } 55 } 56 void DP(int x,int y,int k)//dp具体情况具体分析 57 { 58 decode(dp[pre].sta[k],m); 59 int l=code[y-1]; 60 int up=code[y]; 61 code[y-1]=code[y]=0; 62 memcpy(res,code,sizeof(code)); 63 LL v=dp[pre].sum[k]; 64 if(!l&&!up) 65 { 66 if(gp[x][y]=='*') 67 dp[now].push(encode(m),v); 68 else if(x<n&&y<m&&gp[x+1][y]=='.'&&gp[x][y+1]=='.') 69 { 70 code[y]=code[y-1]=bit; 71 dp[now].push(encode(m),v); 72 } 73 } 74 else if(!l||!up) 75 { 76 int e=l+up; 77 if(x<n&&gp[x+1][y]=='.') 78 { 79 code[y-1]=e; 80 dp[now].push(encode(m),v); 81 memcpy(code,res,sizeof(res)); 82 } 83 if(y<m&&gp[x][y+1]=='.') 84 { 85 code[y]=e; 86 dp[now].push(encode(m),v); 87 } 88 } 89 else if(l!=up) 90 { 91 for(int i=0;i<=m;i++) 92 if(code[i]==up) 93 code[i]=l; 94 dp[now].push(encode(m),v); 95 } 96 else if(x==fx&&y==fy) 97 dp[now].push(encode(m),v); 98 } 99 LL solve() 100 { 101 dp[0].clear();//初始化状态 102 dp[0].push(0,1); 103 now=0,pre=1; 104 for(int i=1;i<=n;i++)//逐格逐状态枚举转移 105 { 106 pre=now,now^=1,dp[now].clear(); 107 for(int k=0;k<dp[pre].size;k++)//轮廓线行转移 108 dp[now].push(dp[pre].sta[k]<<inc,dp[pre].sum[k]); 109 for(int j=1;j<=m;j++) 110 { 111 pre=now,now^=1,dp[now].clear(); 112 for(int k=0;k<dp[pre].size;k++) 113 { 114 DP(i,j,k); 115 } 116 } 117 } 118 for(int i=0;i<dp[now].size;i++) 119 if(dp[now].sta[i]==0) 120 return dp[now].sum[i]; 121 return 0; 122 } 123 int main() 124 { 125 while(~scanf("%d%d",&n,&m)) 126 { 127 for(int i=1;i<=n;i++)//都是从1开始 128 scanf("%s",&gp[i][1]); 129 fx=fy=0; 130 for(int i=n;i>0&&!fx;i--)//寻找最终的位置 131 for(int j=m;j>0&!fx;j--) 132 if(gp[i][j]=='.') 133 fx=i,fy=j; 134 if(fx==0)puts("0"); 135 else cout<<solve()<<endl; 136 } 137 }