震惊！bzoj居然又被苏大佬D飞了。。。
这题煞笔模板题好吧。
然而bzojAC caiojWA%40??? 好强啊
今天早上发现是m打成n了囧
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL mod=100037; int n,m,edx,edy;LL ans; int mp[20][20]; struct Plug { LL f[110000]; int top;LL sta[110000],hash[110000]; void pha(LL s,LL sum) { LL x=s%mod; while(hash[x]!=0&&sta[hash[x]]!=s)x=(x+1)%mod; if(hash[x]==0)sta[++top]=s,hash[x]=top; f[hash[x]]+=sum; } void clean() { top=0; memset(f,0,sizeof(f)); memset(hash,0,sizeof(hash)); } }dp[2]; LL get_bracket(LL s,LL p) { return (s>>(p-1)*2)&3; } LL set_bracket(LL s,LL p,LL v) { s^=(get_bracket(s,p)<<((p-1)*2)); s^=(v<<((p-1)*2)); return s; } int pre,now; void Plug_DP() { pre=0;now=1; dp[now].clean();dp[now].pha(0,1); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { swap(pre,now);dp[now].clean(); for(int k=1;k<=dp[pre].top;k++) { LL s=dp[pre].sta[k],sum=dp[pre].f[k]; LL p=get_bracket(s,j),q=get_bracket(s,j+1); if(mp[i][j]==0) { if(p==0&&q==0) dp[now].pha(s,sum); } else if(mp[i][j]==1) { if(p==0&&q==0) { if(mp[i+1][j]>0&&mp[i][j+1]>0) { s=set_bracket(s,j,1); s=set_bracket(s,j+1,2); dp[now].pha(s,sum); } } else if(p>0&&q==0) { if(mp[i+1][j]>0) { s=set_bracket(s,j,p); s=set_bracket(s,j+1,0); dp[now].pha(s,sum); } if(mp[i][j+1]>0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,p); dp[now].pha(s,sum); } } else if(p==0&&q>0) { if(mp[i+1][j]>0) { s=set_bracket(s,j,q); s=set_bracket(s,j+1,0); dp[now].pha(s,sum); } if(mp[i][j+1]>0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,q); dp[now].pha(s,sum); } } else if(p==1&&q==2) { if(i==edx&&j==edy)ans+=sum; } else if(p==2&&q==1) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); dp[now].pha(s,sum); } else if(p==1&&q==1) { int fd=1; for(int v=j+2;v<=m;v++) { int bck=get_bracket(s,v); if(bck==1)fd++; if(bck==2)fd--; if(fd==0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); s=set_bracket(s,v,1); dp[now].pha(s,sum); break; } } } else if(p==2&&q==2) { int fd=1; for(int v=j-1;v>=1;v--) { int bck=get_bracket(s,v); if(bck==2)fd++; if(bck==1)fd--; if(fd==0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); s=set_bracket(s,v,2); dp[now].pha(s,sum); break; } } } } else if(mp[i][j]==2) { if(p==0&&q>0) { if(mp[i+1][j]>0) { s=set_bracket(s,j,q); s=set_bracket(s,j+1,0); dp[now].pha(s,sum); } } } else if(mp[i][j]==3) { if(p>0&&q==0) { if(mp[i][j+1]>0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,p); dp[now].pha(s,sum); } } } } } for(int k=1;k<=dp[now].top;k++) dp[now].sta[k]<<=2; } } char ss[20]; int main() { scanf("%d%d",&n,&m); memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++) { scanf("%s",ss+1); for(int j=1;j<=m;j++) { if(ss[j]=='.')mp[i][j]=1; else if(ss[j]=='|')mp[i][j]=2; else if(ss[j]=='-')mp[i][j]=3; if(ss[j]!='#')edx=i,edy=j; } } ans=0;Plug_DP(); printf("%lld ",ans); return 0; }