Description：

给出n*m的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？

Hint：

\(n,m<=12\)

Solution:

与原来单回路那题转移方程有些不同，详见代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxn=15,c[4]={0,-1,1,0};

struct data {

    int key; ll val;

};

ll ans;

int n,m,t,ex,ey;

char mp[mxn][mxn];

unordered_map<int ,data > dp[3];

typedef unordered_map<int ,data >::iterator uit;

inline void copy(data x,int id) {dp[id][x.key<<2]=(data){x.key<<2,x.val};} 

inline int get(int st,int x) {x<<=1; return (st>>x)&3;}

inline int md(int st,int x,int val) {x<<=1; return (st&(~(3<<x)))|(val<<x);}

inline int getl(int st,int x) {

    int l=x,cnt=1;

    while(cnt!=0) cnt+=c[get(st,--l)];

    return l;

}

inline int getr(int st,int x) {

    int r=x,cnt=-1;

    while(cnt!=0) cnt+=c[get(st,++r)];

    return r;

}

inline void update(int x,int y,data d)

{

    int st=d.key; ll val=d.val;

    int p=get(st,y),q=get(st,y+1);

    if(mp[x][y]=='*') {

        if(p==0&&q==0) dp[t^1][st]=(data){st,dp[t^1][st].val+val};

        return ;

    }

    if(p==0&&q==0) {

        if(x==n-1||y==m-1) return ;

        int nst=md(st,y,1); nst=md(nst,y+1,2);

        dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val};

        return ;

    }

    if(p==0||q==0) {

        if(y<m-1) {

            int nst=md(st,y,0); nst=md(nst,y+1,p+q);

            dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val};

        }

        if(x<n-1) {

            int nst=md(st,y,p+q); nst=md(nst,y+1,0);

            dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val};

}

        return ;

    }

    int nst=md(st,y,0); nst=md(nst,y+1,0);

    if(p==1&&q==1) nst=md(nst,getr(st,y+1),1);

    if(p==2&&q==2) nst=md(nst,getl(st,y),2);

    if(p==1&&q==2) {

        dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val}; //新增回路

        if(x==ex&&y==ey) ans+=val; //分次数统计答案

        return ;

    }

    if(p==2&&q==1) {

        dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val}; //一右一左直接消掉括号

        return ;

    }

    dp[t^1][nst]=(data){nst,dp[t^1][nst].val+val};

}

int main()

{

    int T;

    cin>>T;

    while(T--) {

    dp[0].clear(),dp[1].clear();

    scanf("%d%d",&n,&m); int tp,flag=0; ans=0;

    for(int i=0;i<n;++i)

        for(int j=0;j<m;++j) {

            scanf("%d",&tp);

            if(tp==1) mp[i][j]='.',++flag;

            else mp[i][j]='*';

        }

        for(int i=0;i<n;++i)

        for(int j=0;j<m;++j)

            if(mp[i][j]=='.') ex=i,ey=j;

    t=0; dp[t][0]=(data){0,1ll};

    for(int i=0;i<n;++i) {

        dp[2].clear();

        for(uit j=dp[t].begin();j!=dp[t].end();++j) copy((*j).second,2);

        dp[t].clear();

        for(uit j=dp[2].begin();j!=dp[2].end();++j) dp[t][(*j).second.key]=(*j).second;

        for(int j=0;j<m;++j) {

            dp[t^1].clear();

            for(uit k=dp[t].begin();k!=dp[t].end();++k)

                update(i,j,(*k).second);

            t^=1;

        }

    }

    if(!flag) {puts("1");continue;} //特判，数据有坑

    printf("%lld\n",ans);

    }

    return 0;

}