题目链接:
题意:给出一个n*m的地面。有些是障碍。用L型的地板砖铺满。有多少种方案。
思路:用0表示没有插头,用1表示有插头且可以拐弯,用3表示有插头但是不能再拐弯了。
设有m列,轮廓线为[0,m]。对于格子(i,j),设左插头x上插头y,那么转移有:
(1)x=0,y=0:此时如图1-0,有三种转移,分别是1-1,1-2,1-3;
(2)x!=0,y!=0:此时只有当x=y=1时可以转移,就是合并插头,如图3-0;
(3)x和y中只有一个不是0。不妨设y=0,x!=0,那次此时若x=3,可以延续或者停止;若x=1,可以合并或者可以拐弯。
struct node{ int st[N],cnt[N],size; int head[HashSize],next[N]; void init() { size=0; clr(head,-1); } void add(int S,int x) { int t=S%HashSize; int i; for(i=head[t];i!=-1;i=next[i]) { if(st[i]==S) { cnt[i]=(cnt[i]+x)%mod; return; } } st[size]=S; cnt[size]=x; next[size]=head[t]; head[t]=size++; }};node f[2];int pre,cur;int n,m;char s[105][105];void init(){ RD(n,m); int i,j; FOR1(i,n) RD(s[i]+1); char s1[105][105]; if(m>n) { FOR1(j,m) FOR1(i,n) s1[j][i]=s[i][j]; swap(n,m); FOR1(i,n) FOR1(j,m) s[i][j]=s1[i][j]; }}int getBit(int st,int k){ return (st>>(k+k))&3;}int set0(int st,int k){ return st&(~(3<<(k+k)));}int set1(int st,int k){ st=set0(st,k); return st|(1<<(k+k));}int set3(int st,int k){ return st|(3<<(k+k));}void add(int S,int x){ f[cur].add(S,x);}void DP(int i,int j){ int k,x,y,S,cnt; FOR0(k,f[pre].size) { S=f[pre].st[k]; cnt=f[pre].cnt[k]; if(j==1) { if(getBit(S,m)) continue; S=S<<2; } x=getBit(S,j-1); y=getBit(S,j); S=set0(S,j-1); S=set0(S,j); if(s[i][j]=='*') { if(x||y) continue; add(S,cnt); continue; } if(!x&&!y) { add(set1(S,j),cnt); add(set1(S,j-1),cnt); S=set3(S,j-1); S=set3(S,j); add(S,cnt); } else if(x&&y) { if(x==1&&y==1) add(S,cnt); } else if(x||y) { if(x==3) add(set3(S,j),cnt),add(S,cnt); else if(x==1) add(set1(S,j),cnt),add(set3(S,j-1),cnt); if(y==3) add(set3(S,j-1),cnt),add(S,cnt); else if(y==1) add(set1(S,j-1),cnt),add(set3(S,j),cnt); } }}int main(){ init(); pre=0; cur=1; f[pre].init(); f[pre].add(0,1); int i,j; FOR1(i,n) FOR1(j,m) { f[cur].init(); DP(i,j); swap(pre,cur); } int ans=0; FOR0(i,f[pre].size) if(f[pre].st[i]==0) ans=f[pre].cnt[i]; PR(ans);}