首页 > 代码库 > BZOJ 2331 地板（插头DP）

BZOJ 2331 地板（插头DP）

2024-07-08 23:54:32   225人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2331

题意：给出一个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);}

 

 

 


联系
我们