柒葉灬 的博客

柒葉灬 的博客

插头DP & 轮廓线DP

posted on 2019-08-11 15:08:38 | under 专题总结 |

插头DP 和 轮廓线DP


专题 A - Mondriaan's Dream (轮廓线DP)

题意: 给你一个 $n\times m $ 的棋盘,用 $1 \times 2$ 的块覆盖整个棋盘,问方案数?( $n,m \in [1,11] $ )

思路: 数据范围很小,考虑用状压DP,单纯的状压DP的话转移起来有点困难,但若考虑单个位置的时候,情况变得简单起来:

  1. 若该位置被覆盖,则不用管它

  2. 若该位置没有被覆盖:(1)摆一个朝下的 (2)摆一个朝右的

普通的状压DP相当于还要枚举每个位置的状态,而轮廓线只要枚举一个就可以了。

具体细节看代码回忆。

#include<cstdio>
#include<cstring>
#include<iostream>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;

int n,m;
bool mark[maxn][maxn];
long long dp[2][1<<11];
int num(int x){return 1<<x-1;}
int getnum(int S,int x){return (S>>x-1)&1;}

int main(){
    while(scanf("%d%d",&n,&m),n&&m){
        memset(mark,0,sizeof(mark));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                mark[i][j]=1;
        memset(dp,0,sizeof(dp));
        int cur=0;
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
                for(int S=0;S<1<<m;S++){
                    int now=getnum(S,j),right=getnum(S,j+1);
                    long long val=dp[cur^1][S];
                    if(now){
                        dp[cur][S^num(j)]+=val;
                    }else {
                        if(mark[i+1][j])
                            dp[cur][S^num(j)]+=val;
                        if(mark[i][j+1]&&!right)
                            dp[cur][S^num(j+1)]+=val;
                    }
                }
            }
        }
        cout<<dp[cur][0]<<endl;
    }
    return 0;
}

专题 B - 方格取数(1)

题意: 中文题面,自己看题

思路: 取一个数的时候只需要关心两个事:

(1)该位置能不能取

(2)这个位置取了会导致哪些位置的数不能取。

用 $1$ 表示这个位置可以取 $0$ 表示不能取,轮廓线DP即可。


专题 C - Pebbles

题意: 给一个 $n \times m$ 的矩阵,从中取出不相邻的若干个数,使得和最大。( $n,m \in [3,15]$ )

(注意,这里相邻包括8个方向)

思路: 跟上一题的方格取数差不多,多加一进制表示这个位置以及下方的位置也不能取即可。


------------- 分 ------------- 割 ------------- 线 -------------

很简单介绍

解决有关连通性状压问题一般考虑到插头 DP,

有关插头DP的文章:插头DP

注意:一定要区分最小表示法括号配对法 不然会很乱,还有对于配对指的是两个插头当前在一个连通块内

写多了题目形成自己的板子就行了。


专题 D - Eat the Trees

题意: 给 $n\times m$ 的矩阵,矩阵上有一些障碍,找任意个回路覆盖全部非障碍格子,求方案数。( $ n ,m \in [1,11]$ )

思路: 由于不需要形成唯一回路,所以可以只记录有没有插头,至于左插头还是右插头可以不用管。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;
int n,m;
long long dp[maxn][1<<13];
bool mark[maxn][maxn];
int getnum(int S,int x){
    return (S>>(x-1))&1;
}
int num(int x){
    return 1<<x-1;
}
int main(){
    for(int _,cas=(cin>>_,1);cas<=_;cas++){
        scanf("%d%d",&n,&m);
        memset(mark,0,sizeof(mark));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&mark[i][j]);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        int cur=0;
        for(int i=1;i<=n;i++){
            cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
            for(int S=0;S<1<<m;S++)
                dp[cur][S<<1]=dp[cur^1][S];

            for(int j=1;j<=m;j++){
                cur^=1;memset(dp[cur],0,sizeof(dp[cur]));

                for(int S=0;S<1<<m+1;S++){
                    int left=getnum(S,j),up=getnum(S,j+1);
                    long long val=dp[cur^1][S];
                    if(!mark[i][j]){
                        if(!left&&!up)dp[cur][S]+=val;
                    }else if(!left&&!up){
                        if(mark[i+1][j]&&mark[i][j+1])
                            dp[cur][S^num(j)^num(j+1)]+=val;
                    }else if(!left&&up){
                        if(mark[i+1][j])
                            dp[cur][S^num(j)^num(j+1)]+=val;
                        if(mark[i][j+1])
                            dp[cur][S]+=val;
                    }else if(left&&!up){
                        if(mark[i+1][j]);
                            dp[cur][S]+=val;
                        if(mark[i][j+1])
                            dp[cur][S^num(j)^num(j+1)]+=val;
                    }else if(left&&up){
                        dp[cur][S^num(j)^num(j+1)]+=val;
                    }
                }
            }
        }
        printf("Case %d: There are %lld ways to eat the trees.\n",cas,dp[cur][0]);
    }
    return 0;
}

专题E - Formula 1 (插头DP) 真·入门题

题意: 给 $n\times m$ 的矩阵,矩阵上有一些障碍,找一个回路覆盖全部非障碍格子,求方案数。( $ n ,m \in [2,12]$ )

思路: 这题不能像上一题一样只记录有没有插头了,因为如果形成多个回路就完了,需要记录该插头是左插头还是右插头。

(左插头的意思其实就是一个联通路径的左边插头)

在处理每一个格子的时候,相邻的只有左边和上面,

所以记左边插头状态为 $left$ ,上边的插头状态为 $up$

$0$ 表示没有插头, $1$ 表示是个左插头, $2$ 表示是个右插头

形成回路的点必须是最后一个,否则就可能出现多个回路。

每一对左插头右插头配对了,就说明多了一个回路,

而这题只能有一个,所以在最后的时候配对就行了,

大力分类讨论:

  1. 如果这个点是障碍,那么必须 $left==0\ and \ up==0$ 才能转移

  2. 如果 $ !left \ and \ !up$ 那么必须创造一个向下且向右的新插头(每个空格必须覆盖)

  3. 如果 $left \ and \ !up$ ,那么左插头要么延伸向下,要么向右,分两种情况讨论

  4. 如果 $!left \ and \ up$ ,同第 $3$ 种情况

  5. 如果 $left==1 \ and \ up==1$ 两个左插头碰在一起,那么连起来之后,对应的两个右插头则相应变为一对,其中左边的变为左插头。(模拟一下就想明白了)

  6. 如果 $left==2 \ and \ up==2 $ 两个右插头碰在一起,那么连起来之后,对应的两个左插头则相应变为一对,其中右边的变为右插头。(模拟一下就想明白了)

  7. 如果 $left==2 \ and \ up==1 $ 左边是右插头,右边是左插头,说明左右两个连通块连在了一起,模拟一下发现对应的两个插头都不需要改变。

  8. 如果 $left==1 \ and \ up==2 $ 左边左插头,右边右插头,说明要产生新的回路了,此时判断这个点是不是最后一个点,如果是则加入答案,否则就是不合法状态了。


看似转移情况很多,实际上很多时候在复制粘贴 自己写的时候只要自己模拟一下就行了,想通了话理解就能写出来了。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;
bool cur1;
int n,m,ex,ey;
long long ans;
char mp[maxn][maxn];
bool mark[maxn][maxn];

const int P=2333;
struct DP{
    int tot,head[P],st[maxm],nxt[maxm];
    long long sum[maxm];
    void clear(){
        memset(head,0,sizeof(head));tot=0;
    }
    int size(){return tot;}
    void insert(int S,long long val){
        int x=S%P;
        for(int i=head[x];i;i=nxt[i]){
            if(st[i]==S){
                sum[i]+=val;
                return;
            }
        }
        st[++tot]=S;sum[tot]=val;
        nxt[tot]=head[x];head[x]=tot;
    }
}dp[2];
int getnum(int S,int x){
    return (S>>((x-1)*2))&3;
}
int num(int x,int p){
    return p<<(x-1<<1);
}
int main(){
    while(cin>>n>>m){
        memset(mark,0,sizeof(mark));
        for(int i=1;i<=n;i++){
            scanf("%s",mp[i]+1);
            for(int j=1;j<=m;j++){
                if(mp[i][j]=='.'){
                    ex=i;ey=j;
                    mark[i][j]=1;
                }
            }
        }
        int cur=0;
        ans=0;
        dp[0].clear();
        dp[0].insert(0,1);
        for(int i=1;i<=n;i++){

            for(int j=1;j<=dp[cur].size();j++)
                dp[cur].st[j]<<=2;

            for(int j=1;j<=m;j++){
                cur^=1;dp[cur].clear();
                for(int k=1;k<=dp[cur^1].size();k++){
                    int S=dp[cur^1].st[k];
                    long long val=dp[cur^1].sum[k];
                    int left=getnum(S,j),up=getnum(S,j+1);
                    if(!mark[i][j]){
                        if(!left&&!up)
                            dp[cur].insert(S,val);
                    }else if(!left&&!up){
                        if(mark[i+1][j]&&mark[i][j+1])
                            dp[cur].insert(S+num(j,1)+num(j+1,2),val);
                    }else if(left&&!up){
                        if(mark[i+1][j])
                            dp[cur].insert(S,val);
                        if(mark[i][j+1])
                            dp[cur].insert(S^num(j,left)^num(j+1,left),val);
                    }else if(!left&&up){
                        if(mark[i][j+1])
                            dp[cur].insert(S,val);
                        if(mark[i+1][j])
                            dp[cur].insert(S^num(j+1,up)^num(j,up),val);
                    }else if(left==1&&up==1){
                        int cnt=1;
                        for(int l=j+2;l<=m+1;l++){
                            if(getnum(S,l)==1)cnt++;
                            else if(getnum(S,l)==2){
                                cnt--;
                                if(cnt==0){
                                    S-=num(l,1);
                                    break;
                                }
                            }
                        }
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==2&&up==1){
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==2&&up==2){
                        int cnt=1;
                        for(int l=j-1;l>=1;l--)
                            if(getnum(S,l)==1){
                                cnt--;
                                if(cnt==0){
                                    S+=num(l,1);
                                    break;
                                }
                            }else if(getnum(S,l)==2)cnt++;
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==1&&up==2){
                        if(i==ex&&j==ey)
                            ans+=val;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

专题F

F题题意:一个NM的图,其中X表示障碍,表示空地,O表示必经点,求走一条回路经过所有必经点右多少种方案。

思路:对于空的格子可以有两种选择,加入插头或者不加入,终止状态则变成经过必经点后面的点。


专题G

G题题意:一个n*m的房子,输入如样例,每个空格表示一个房间,数字表示把两个相邻的房间连起来所需的费用,#表示墙,求把所有房间连成一条回路的最小代价。

思路:在延伸出插头的时候加入权值防止重复或者漏加


专题H

H题题意:一个n*m矩阵,求从左上角走到右下角(路径可以不经过所有点,但不能重复走一个点)的最小代价。

思路:(1)从外面加一条不存在的路线,使得形成回路 (2)引入独立插头进行DP

解法(1)更为方便


专题I

I题题意:一个n*m的图,#表示障碍,求从左下角走到右下角,经过所有非障碍点的路径方案数。

思路:与上题相似


专题J

J题题意:一个n*m的图,0表示空地,1表示障碍,2/3表示2/3这条线的一个端点(2/3只会出现两次),求把2个2和2个3连起来且不相交的最短长度-2的值(可以看看题面的图)。如果无解输出0 。

思路:这题看似需要简单路径,其实并不,因为求得是路径长度和最短的,所以就算出现了无用的回路也无所谓,肯定会被最优解覆盖,所以插头就变成了 属于2还是属于3 两种插头。


专题K

K题题意:一个蜂巢,它有n行8列,编号见图,输入m个坐标表示障碍,求用多条回路铺满整个蜂巢有多少种方案。

思路:这题就是轮廓线多了几条边而已,分奇偶讨论不同轮廓线状态,代码有bug会极其难调


专题L

L题题意:一个n*m的图求从左上角走到左下角,经过所有点,有多少种方案,如果没有输出Impossible (2 <= N <= 7, 1 <= M <=10^9)

思路:m有点大,考虑矩阵快速幂,矩阵快速幂的时候不能形成回路,要特殊处理最后一排,因为 n<=7 爆搜出来的状态数不超过130,所以复杂度有保证。


专题M(独立插头的应用)

M题题意:一个n*m的矩阵,0表示障碍,其他数表示这个点的权值,求从任意起点出发,在任意终点结束(路径上的点不能重复走)的路径中,权值最大是多少。

思路:因为是一条路径,而且起点终点任意,所以需要引入独立插头,在每一个状态都不能同时存在大于2的独立插头,有的话不转移就行了。

独立插头的转移可以看插头DP开头放出来的博客,

或者说看代码(5K)理解。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=20;
int n,m;
int ans,mark[maxn][maxn];
const int P=23333,maxm=1e6;
struct DP{
    int tot,head[P],st[maxm],nxt[maxm];
    int mx[maxm];
    void insert(int S,int val){
        int x=S%P;
        for(int i=head[x];i;i=nxt[i]){
            if(st[i]==S){
                mx[i]=max(mx[i],val);
                return;
            }
        }
        st[++tot]=S;mx[tot]=val;
        nxt[tot]=head[x];head[x]=tot;
    }
    void clear(){
        memset(head,0,sizeof(head));
        tot=0;
    }
    int size(){
        return tot;
    }
}dp[2];
int getnum(int S,int x){
    return (S>>(x-1<<1))&3;
}
int num(int x,int p){
    return p<<(x-1<<1);
}
bool check(int S){
    int cnt=0;
    while(S){
        if((S&3)==3)cnt++;
        S>>=2;
    }
    return cnt<3;
}
int main(){
    for(int _=(cin>>_,_);_--;){
        scanf("%d%d",&n,&m);
        ans=0;
        memset(mark,0,sizeof(mark));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                scanf("%d",&mark[i][j]);
                ans=max(ans,mark[i][j]);
            }

        int cur=0;
        dp[0].clear();
        dp[0].insert(0,0);
        for(int i=1;i<=n;i++){
            for(int k=1;k<=dp[cur].size();k++)
                dp[cur].st[k]<<=2;

            for(int j=1;j<=m;j++){
                cur^=1;dp[cur].clear();

                for(int k=1;k<=dp[cur^1].size();k++){
                    int S=dp[cur^1].st[k];
                    if(!check(S))continue;
                    int val=dp[cur^1].mx[k];

                    int left=getnum(S,j);
                    int up=getnum(S,j+1);
                    if(!mark[i][j]){
                        if(!left&&!up)dp[cur].insert(S,val);
                        continue;
                    }
                    val+=mark[i][j];
                    if(!left&&!up){
                        dp[cur].insert(S,val-mark[i][j]);
                        if(mark[i+1][j]&&mark[i][j+1])
                            dp[cur].insert(S^num(j,1)^num(j+1,2),val);
                        if(mark[i+1][j])
                            dp[cur].insert(S^num(j,3),val);
                        if(mark[i][j+1])
                            dp[cur].insert(S^num(j+1,3),val);
                    }else if(!left&&up){
                        if(mark[i+1][j]){
                            dp[cur].insert(S^num(j,up)^num(j+1,up),val);
                        }
                        if(mark[i][j+1])
                            dp[cur].insert(S,val);
                        if(up==1){
                            int cnt=1;
                            for(int l=j+2;;l++){
                                if(getnum(S,l)==1)cnt++;
                                else if(getnum(S,l)==2){
                                    cnt--;
                                    if(cnt==0){
                                        S+=num(l,1);
                                        break;
                                    }
                                }
                            }
                            dp[cur].insert(S^num(j+1,up),val);
                        }else if(up==2){
                            int cnt=1;
                            for(int l=j-1;;l--){
                                if(getnum(S,l)==2)cnt++;
                                else if(getnum(S,l)==1){
                                    cnt--;
                                    if(cnt==0){
                                        S+=num(l,2);
                                        break;
                                    }
                                }
                            }
                            dp[cur].insert(S^num(j+1,up),val);
                        }else {
                            S^=num(j+1,3);
                            if(S==0)ans=max(ans,val);
                        }
                    }else if(left&&!up){
                        if(mark[i+1][j])
                            dp[cur].insert(S,val);
                        if(mark[i][j+1])
                            dp[cur].insert(S^num(j,left)^num(j+1,left),val);
                        if(left==1){
                            int cnt=1;
                            for(int l=j+2;;l++){
                                if(getnum(S,l)==1)cnt++;
                                else if(getnum(S,l)==2){
                                    cnt--;
                                    if(cnt==0){
                                        S+=num(l,1);
                                        break;
                                    }
                                }
                            }
                            dp[cur].insert(S^num(j,left),val);
                        }else if(left==2){
                            int cnt=1;
                            for(int l=j-1;;l--){
                                if(getnum(S,l)==2)cnt++;
                                else if(getnum(S,l)==1){
                                    cnt--;
                                    if(cnt==0){
                                        S+=num(l,2);
                                        break;
                                    }
                                }
                            }
                            dp[cur].insert(S^num(j,left),val);
                        }else {
                            S^=num(j,3);
                            if(S==0)ans=max(ans,val);
                        }
                    }else if(left==1&&up==1){
                        int cnt=1;
                        for(int l=j+2;;l++){
                            if(getnum(S,l)==1)cnt++;
                            else if(getnum(S,l)==2){
                                cnt--;
                                if(cnt==0){
                                    S-=num(l,1);
                                    break;
                                }
                            }
                        }
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==2&&up==2){
                        int cnt=1;
                        for(int l=j-1;;l--){
                            if(getnum(S,l)==2)cnt++;
                            else if(getnum(S,l)==1){
                                cnt--;
                                if(cnt==0){
                                    S+=num(l,1);
                                    break;
                                }
                            }
                        }
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==2&&up==1){
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==1&&up==3||left==3&&up==1){
                        int cnt=1;
                        for(int l=j+2;;l++){
                            if(getnum(S,l)==1)cnt++;
                            else if(getnum(S,l)==2){
                                cnt--;
                                if(cnt==0){
                                    S+=num(l,1);
                                    break;
                                }
                            }
                        }
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==2&&up==3||left==3&&up==2){
                        int cnt=1;
                        for(int l=j-1;;l--){
                            if(getnum(S,l)==2)cnt++;
                            else if(getnum(S,l)==1){
                                cnt--;
                                if(cnt==0){
                                    S+=num(l,2);
                                    break;
                                }
                            }
                        }
                        dp[cur].insert(S^num(j,left)^num(j+1,up),val);
                    }else if(left==3&&up==3){
                        S^=num(j,left)^num(j+1,up);
                        if(S==0)ans=max(ans,val);
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

专题N

N题题意:一个nm的矩阵,表示障碍,每个点都必须在一个环上,且环之间不能嵌套(大环套小环),求恰好形成K个环的方案数。

思路:大环不能套小环是个很麻烦的事情,如何处理这个是本题的关键,有一个神奇的做法就是形成回路的时候左右配对的括号必须是偶数,一方面可以保证可以有方案使得没有环嵌套自己,也能让这个环没有嵌套别的环。


当初为什么要学插头DP呢,就是为了解决这个题目↓

「CTSC2010」产品销售 $\ \ \ \ \ \ \ \ \ \ $ ← 写个专题就是为了能A了这题!

↑ ↑ 对就是他,这题就算知道是插头DP也不一定搞得出来 ↑

是一个好题 (毒瘤)

题目在203上的#262


上面说过,一般的插头DP解决的是连通性状压问题

基础的就是回路了,拓展一下就是路径。

而这题不仅是路径还带有方向,所以需要改变一下插头的定义,

不能再是简单的左插头右插头了,

对于带有方向的路径问题:

  1. 设插头0为没有插头

  2. 设插头1为向起点方向走的

  3. 设插头2为向终点方向走的

这样子可以保证既不产生回路(显然),

又能保证一个状态的表示

(那之前有一个用独立插头的那题?能不能这么写呢?待补)

这题需要知道上一次填的数是什么,下一步是变大还是变小,

前者压8位,后者压2位,用10位二进制表示一个状态。


这一压之后还有一个问题就是,

怎么获知哪些数被取过了?

先给出结论,对于一个状态,唯一对应一种取法,

具体证明,详见枚举结果:)

↓ 模拟成果

这里设3个插头分别为ABC,

默认若在同种插头状态下 权值A<权值B<权值C

一、有3个插头的情况

  1. ABC都向小:不存在(只有一个起点)

  2. AB向小,C向大:权值较大B肯定是从终点来的,A与C构成联通。——被取的区间为 $ [B,n*m] $ 和 $ [A,C] $ 。为什么C不与较大的B联通不用说了吧?

  3. A向小,BC向大:权值较小B肯定是从起点来的,A与C构成联通。——被取的区间为 $[1,B]$ 和 $[A,C]$ 。

  4. ABC都向大:不存在(只有一个终点)

二、有2个插头的情况

  1. AB都向小:不存在(只有一个起点)

  2. A向小,B向大:被取的区间为 $[A,B]$ 。

  3. AB都向大:不存在(只有一个终点)

三、有1个插头的情况

  1. A向小:被取的区间为 $[A,n*m]$

  2. A向大:被取的区间为 $[1,A]$

四、有0个插头的情况

  1. 初始状态和最终状态

如果觉得上述方法过于麻烦,可以用bitset

接着就是常规插头DP的分类讨论,

这里省略了01值相等是否的判断

设左边的权值为 $leftnum$ ,状态为 $leftst$

设上边的权值为 $upnum$ ,状态为 $upst$

一、 $leftst==0\ \ \&\&\ \ upst==0 $

  1. 插入 $[2,n*m-1]$ 的值,

  2. 插入 $n*m$

  3. 插入 $1$ ,一定要注意起点在边界上

二、 $leftst≠0\ \ \&\&\ \ upst==0 $

  1. 插头延伸向下。

  2. 插头延伸向右。

  3. 注意延伸到头的情况,尤其是到了起点的情况。

三、 $leftst==0\ \ \&\&\ \ upst≠0 $

  1. 插头延伸向下。

  2. 插头延伸向右。

  3. 注意延伸到头的情况,尤其是到了起点的情况。

四、 $leftst≠0\ \ \&\&\ \ upst≠0 $

  1. 如果 $leftst==upst$ :不合法

  2. 如果插头对应的后一个权值不一样:不合法

  3. 合法就将两个插头接在一起。

(对于是否取过的判断在check的结构体内,对于插头的连接在main函数里面)

最后贴上代码

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=55,P=11192869;
int n,m;
int A[4][maxn],B[maxn*3];
char str[maxn*3];

const int P2=233341,maxm=2e5;
struct DP{
    int tot,head[P2],nxt[maxm],sum[maxm];
    long long st[maxm];
    int size(){
        return tot;
    }
    void clear(){
        memset(head,0,sizeof(head));
        tot=0;
    }
    void insert(long long S,int val){
        int x=S%P2;
        for(int i=head[x];i;i=nxt[i]){
            if(st[i]==S){
                sum[i]=(sum[i]+val)%P;
                return;
            }
        }
        st[++tot]=S;sum[tot]=val;
        nxt[tot]=head[x];head[x]=tot;
    }
}dp[2];
int get(long long S,int x){
    return (S>>(x-1)*10)&1023;
}
int getst(long long S,int x){//1表示向小 2表示向大 
    return get(S,x)&3;
}
int getnum(long long S,int x){
    return get(S,x)>>2;
}
long long num(int val,int st,int p){
    return 1LL*(val<<2|st)<<(p-1)*10;
}
struct Check{
    int id;
    struct node{
        int op,x;
        bool operator <(const node &_)const{
            return op!=_.op?op<_.op:x<_.x;
        }
    }A[4];
    void add(int S){
        if(!S)return;
        A[++id]=(node){S&3,S>>2};
    }
    void init(long long S){
        id=0;
        while(S){
            add(S&1023);
            S>>=10;
        }
        sort(A+1,A+1+id);
    }
    bool check(int x){
        if(id==3){
            if(A[2].op==1){
                if(x>=A[2].x)return false;
                if(x>=A[1].x&&x<=A[3].x)return false;
            }else {
                if(x<=A[2].x)return false;
                if(x>=A[1].x&&x<=A[3].x)return false;
            }
        }if(id==2){
            if(x>=A[1].x&&x<=A[2].x)return false;
        }else if(id==1){
            if(A[1].op==1){
                if(x>=A[1].x)return false;
            }else {
                if(x<=A[1].x)return false;
            }
        }
        return true;
    }
}T;
int main(){
//  freopen("trip.in","r",stdin);
//  freopen("trip.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
            A[i][j]=(str[j]=='1');
    }
    scanf("%s",str+1);
    for(int i=1;i<=n*m;i++)
        B[i]=(str[i]=='1');

    int cur=0;
    dp[0].insert(0,1);
    for(int j=1;j<=m;j++){
        for(int k=1;k<=dp[cur].size();k++)
            dp[cur].st[k]<<=10;
        for(int i=1;i<=n;i++){
            cur^=1;dp[cur].clear();
            for(int k=1;k<=dp[cur^1].size();k++){
                long long S=dp[cur^1].st[k];
                int val=dp[cur^1].sum[k];
                T.init(S);
                int leftst=getst(S,i),leftnum=getnum(S,i);
                int upst=getst(S,i+1),upnum=getnum(S,i+1);
                if(!leftst&&!upst){
                    if(B[n*m]==A[i][j]&&T.check(n*m)){
                        if(i<n)dp[cur].insert(S^num(n*m,1,i+1),val);
                        if(j<m)dp[cur].insert(S^num(n*m,1,i),val);
                    }
                    if(B[1]==A[i][j]&&T.check(1)&&(i==1||i==n||j==1||j==m)){
                        if(i<n)dp[cur].insert(S^num(1,2,i+1),val);
                        if(j<m)dp[cur].insert(S^num(1,2,i),val);
                    }
                    if(i<n&&j<m){
                        for(int l=2;l<n*m;l++){
                            if(B[l]==A[i][j]&&T.check(l)){
                                dp[cur].insert(S^num(l,1,i)^num(l,2,i+1),val);
                                dp[cur].insert(S^num(l,2,i)^num(l,1,i+1),val);
                            }
                        }
                    }
                }else if(!leftst&&upst){
                    int now=upnum+upst*2-3;
                    if(A[i][j]!=B[now]||!T.check(now))continue;
                    S^=num(upnum,upst,i+1);
                    if(now==n*m){
                        dp[cur].insert(S,val);
                    }else if(now==1){
                        if(i==1||j==1||i==n||j==m)dp[cur].insert(S,val);
                    }else {
                        if(i<n)dp[cur].insert(S^num(now,upst,i+1),val);
                        if(j<m)dp[cur].insert(S^num(now,upst,i),val);
                    }
                }else if(leftst&&!upst){
                    int now=leftnum+leftst*2-3;
                    if(A[i][j]!=B[now]||!T.check(now))continue;
                    S^=num(leftnum,leftst,i);
                    if(now==n*m){
                        dp[cur].insert(S,val);
                    }else if(now==1){
                        if(i==1||j==1||i==n||j==m)dp[cur].insert(S,val);
                    }else {
                        if(i<n)dp[cur].insert(S^num(now,leftst,i+1),val);
                        if(j<m)dp[cur].insert(S^num(now,leftst,i),val);
                    }
                }else if(leftst&&upst){
                    int now=leftnum+leftst*2-3;
                    if(upnum+upst*2-3!=now||upst==leftst||!T.check(now))continue;
                    if(A[i][j]!=B[now])continue;
                    dp[cur].insert(S^num(upnum,upst,i+1)^num(leftnum,leftst,i),val);
                }
            }
        }
    }
    printf("%d\n",dp[cur].sum[1]);
    return 0;
}