毒瘤动规-----插头dp

近期图床经常崩掉，如其中图片无法显示，请移步博客园\Longrightarrow更好的食用

插头dp:

$B:$一种基于连通性状态压缩的动态规划问题 $A:$请问有什么应用呢？ $B:$各种网格覆盖问题，范围允许状压解决，常用于计算方案数与联通块权值 $A:$轮廓线与插头呢？？？ $B:$轮廓线是状压的部分，用于解决插头的情况，不同于常见的状压dp，为了更好地处理状态，通常要要到括号表示法、最小表示法等，插头是格与格中的转移，可理解成将拼图连接的位置 $A:$本文将讲解哪些类型的题目呢？ $B:$单回路覆盖方案数，多回路覆盖方案数，骨牌覆盖，联通块最大权，单回路最大权，最小联通块方案，特殊型覆盖，多种限制的最大权 $A:$那我们开始吧！！ **各种例题：** ps：以下的图都并非唯一状态，基于让读者更好理解采用最经典的图例 ## 模板： [P5056 【模板】插头dp](https://www.luogu.org/problemnew/show/P5056) 题目大意 >给出n*m的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？n,m(2<=n,m<=12) 状态： 此题面对一种状态，只考虑格子上方（我们叫它下插头）和左方（我们叫它右插头）插头情况，因为暂时只被这两个插头所影响，通过对插头不同情况的处理完成状态转移 此格与下一格的轮廓线如下图   状态转移实际如下  $b1$ 、$b2$分别表示右插头和下插头 我们知道一条线，是有左端点和右端点的，$0$表示无插头，$1$表示左端点，$2$表示右端点 来看这副图，在$(3,4)$轮廓线上有四个插头，**括号表示法**状态：(##)(##)，四进制表示此状态：$10021002$，明明只出现$0$ $1$ $2$，为什么不用三进制？因为位移更方便 以前的状压不是通常有就为$1$无就为$0$吗？ 那我们为什么这里要用括号匹配四进制，因为$b1==2$ $and$ $b2==1$和$b1==1$ $and$ $b2==2$的状态产生的结果截然不同，不懂没关系，慢慢来，后文自有介绍  **当前点不能走(障碍)** $(1)$ 则$!b1$ $and$ $!b2$才能产生状态转移，有插头就代表会走到该点， 不能走当然得两边都没有插头，，转移后当然这两小段插头也为空，直接添加状态就好了，这里就不放图了，脑补$qwq

当前点能走(非障碍必须走)

 $(2)$ $!b1$ $and$ $b2$只有一个插头，该插头向下延伸，选择直走或往右拐，等同于延续一个连通分量 此时插头的括号状态不变，通俗地说，就是插头本来是几转移后也是几 注意，插头在轮廓线上的位置变了，如果直走$b2$的位置为$0$，$b1$为原来的$b2

  $(4)$ $b1==1$ $and$ $b2==1$ 两个插头相遇，等同于合并两个连通分量，下一次$b1$和$b2$的位置就为$0$了 但这里合并后并非直接删去插头即可，因为这样就只剩下两个右插头了，起不了匹配的效果 得$O(m)$往右扫找另一边匹配的右括号，让两个右括号匹配 而我们 为什么要匹配？ 因为要求一条回路，$b1==2$ $and$ $b2==1$和$b1==1$ $and$ $b2==2$的状态产生的结果截然不同(请看下文)，必须要注意 **括号匹配**  $(5)$ $b1==2$ $and$ $b2==2$ 和上面一样$O(m)$往左扫找另一边的左括号，让两个左括号匹配，脑补吧$qwq (6)$ $b1==2$ $and$ $b2==1$ 直接删掉两个插头(闭合)就好了，不需要处理另一端的插头了，两边的插头会自动匹配$(1212->1002)

 本题利用$hash$和滚动节省空间，为方便与快捷用位运算实现四进制，具体细节看代码， 或许你看到每行之间多了一个这样的状态转移，在此提一下，相当于到每行第一个格子时，前面补一个空插头，剩下的部分从上一行最后一个格子那里直接搬过来  ```cpp for(LL j=1;j<=cnt[now];++j) que[now][j]<<=2; ``` 可能你会想，这八种情况，真的能把所有情况全表示出来吗，我们来看一张图 这种情况怎么来呢，是由$(3,4)$的下插头向下延伸与$(3,2)$的下插头一直向右延伸交由$(4,3)

然后由(4),(5),(6),(7)的某种转移而来

当然，可以严格证明出所有状态都能有上面的八种情况得到，因为只需要所有状态都在情况内

My complete code：

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=13;
const LL hs=299987;
LL n,m,ex,ey,now,last,ans;
LL a[maxn][maxn],head[300000],next[2<<24],que[2][2<<24],val[2][2<<24],cnt[2],inc[13];
inline void init(){
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;++i){
        char s[100];
        scanf(" %s",s+1);
        for(LL j=1;j<=m;++j){
            if(s[j]=='.'){
                a[i][j]=1;
                ex=i; ey=j;
            }
        }
    }
    inc[0]=1;
    for(LL i=1;i<=13;++i)
        inc[i]=inc[i-1]<<2;
}
inline void insert(LL bit,LL num){
    LL u=bit%hs+1;
    for(LL i=head[u];i;i=next[i]){
        if(que[now][i]==bit){
            val[now][i]+=num;
            return;
        }
    }
    next[++cnt[now]]=head[u];
    head[u]=cnt[now];
    que[now][cnt[now]]=bit;
    val[now][cnt[now]]=num;
}
inline void work(){
    cnt[now]=1; val[now][1]=1; que[now][1]=0;
    for(LL i=1;i<=n;++i){
        for(LL j=1;j<=cnt[now];++j)
            que[now][j]<<=2;
        for(LL j=1;j<=m;++j){
            memset(head,0,sizeof(head));
            last=now; now^=1;
            cnt[now]=0;
            for(LL k=1;k<=cnt[last];++k){
                LL bit=que[last][k],num=val[last][k];
                LL b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
                if(!a[i][j]){
                    if(!b1&&!b2)
                        insert(bit,num);
                }else if(!b1&&!b2){
                    if(a[i+1][j]&&a[i][j+1])
                        insert(bit+inc[j-1]+inc[j]*2,num);
                }else if(!b1&&b2){
                    if(a[i][j+1])
                        insert(bit,num);
                    if(a[i+1][j])
                        insert(bit-inc[j]*b2+inc[j-1]*b2,num);
                }else if(b1&&!b2){
                    if(a[i+1][j])
                        insert(bit,num);
                    if(a[i][j+1])
                        insert(bit-inc[j-1]*b1+inc[j]*b1,num);
                }else if(b1==1&&b2==1){
                    LL k1=1;
                    for(LL l=j+1;l<=m;++l){
                        if((bit>>(l*2))%4==1)
                            ++k1;
                        if((bit>>(l*2))%4==2)
                            --k1;
                        if(!k1){
                            insert(bit-inc[j]-inc[j-1]-inc[l],num);
                            break;
                        }
                    }
                }else if(b1==2&&b2==2){
                    LL k1=1;
                    for(LL l=j-2;l>=0;--l){
                        if((bit>>(l*2))%4==1)
                            --k1;
                        if((bit>>(l*2))%4==2)
                            ++k1;
                        if(!k1){
                            insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                            break;
                        }
                    }
                }else if(b1==2&&b2==1){
                    insert(bit-inc[j-1]*2-inc[j],num);
                }else if(i==ex&&j==ey){
                    ans+=num;
                }
            }
        }
    }
}
int main(){
    init();
    work();
    printf("%lld",ans);
    return 0;
}

来放松一下吧

P5074 Eat the Trees

其实对于刚学插头dp也较难完成，但建议读者先独立思考

题目大意

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

上一题的转化题，可以形成多个回路了，b1 and b2时虽然1与2 实际上对整体情况有影响，但对状态转移无影响

怎么理解呢？上一题的括号匹配提过，再加上此题可以形成多条回路，所以实际情况肯定会有影响；至于状态转移，反正我们只需要把加方案数，自然无影响

此题不需要括号匹配，多条回路b1 and b2实际闭合删插头，用二进制，1表示有插头，0表示无插头

ps：如果整个图都没有1，只有0，也算一种合法方案！

上一题放的是hash代码，为了让大家更熟悉，这里放个费空间的

#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL maxn=13;
const LL hs=299987;
LL n,m,now,last,ans,kase,T,M,up;
LL a[maxn][maxn],inc[maxn],dp[maxn][maxn][1<<maxn];
inline LL read(){
    LL x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0'; c=getchar();
    }return x*f;
}
inline void solve(){
    memset(dp,0,sizeof(dp));
    dp[0][m][0]=1;
    for(LL i=1;i<=n;++i){
        for(LL j=0;j<=up;++j)
            dp[i][0][j<<1]=dp[i-1][m][j];
        for(LL j=1;j<=m;++j){
            for(LL k=0;k<=up;++k){
                LL bit=k,num=dp[i][j-1][k];
                LL b1=(bit>>(j-1))&1,b2=(bit>>(j))&1;
                if(!a[i][j]){
                    if(!b1&&!b2)
                        dp[i][j][bit]+=num;
                }else if(!b1&&!b2)
                    dp[i][j][bit+inc[j-1]+inc[j]]+=num;
                else if(!b1&&b2){
                    if(a[i][j+1])
                        dp[i][j][bit]+=num;
                    if(a[i+1][j])
                        dp[i][j][bit+inc[j-1]-inc[j]]+=num;
                }else if(b1&&!b2){
                    if(a[i][j+1])
                        dp[i][j][bit-inc[j-1]+inc[j]]+=num;
                    if(a[i+1][j])
                        dp[i][j][bit]+=num;
                }else
                    dp[i][j][bit-inc[j-1]-inc[j]]+=num;
            }
        }
    }
    //printf("Case %lld: There are %lld ways to eat the trees.\n",++kase,dp[n][m][0]);
    printf("%lld\n",dp[n][m][0]);
}
int main(){
    T=read();
    inc[0]=1;
    for(LL i=1;i<=13;++i)
        inc[i]=inc[i-1]<<1;
    while(T--){
        n=read(); m=read();
        up=(1<<(m+1))-1;
        for(LL i=1;i<=n;++i)
            for(LL j=1;j<=m;++j)
                a[i][j]=read();
        solve();
    }
    return 0;
}/*
*/

P3886 [JLOI2009]神秘的生物

题目大意

n*n的带权网格，求某个联块的最大和 n<=9

这里不需要形成回路，而是经典的联通块题，上面的方法无用武之地了(判断联通)，通常我们采取最小表示法

此题的轮廓线有所不同，因为两相邻块均选是直接联通的，如下图   每个方格有两种基本状态 **不选** 当然得考虑状态合理，无下插头或下插头所在联通块还有其他插头，否则下插头被孤立而不形成联通块了 大家发现没有？ 这里每个状态仅合理而已，并不能确定这是可取的最终状态，因为最后得保证只有一个联通块(其实上文也)，详细请看$update

那为什么不考虑右插头呢？而要判断下插头呢？

因为下插头以后再也不会判断了，所以要考虑状态合理，右插头到下一行自然会考虑状态

右插头来自上一个转移状态，很可能形成新块7，故这样转移条件会变得严苛，最终答案通常会小于正确答案

选

$(2)$ $b1$ $or$ $b2$ 此块与插头相连，更新联通块状态，这就是伟大的最小表示法 ```cpp s[j]=max(b1,b2); for(LL l=1;l<=m;++l) if(s[l]&&s[l]==min(b1,b2)) s[l]=max(b1,b2); ``` $Ps$：在$updateup$时，只有当存在唯一联通块时才$update$ $ans

My complete code：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=24;
const LL hs=299987;
LL n,ans=-2*1e9,now=0,last=1;
LL val[2][1<<maxn],que[2][1<<maxn],next[1<<maxn],head[300000],a[maxn][maxn],cnt[2],inc[maxn],s[maxn];
inline void insert(LL bit,LL num){
    LL u=bit%hs+1;
    for(LL i=head[u];i;i=next[i]){
        if(que[now][i]==bit){
            val[now][i]=max(val[now][i],num);
            return;
        }
    }
    next[++cnt[now]]=head[u];
    head[u]=cnt[now];
    que[now][cnt[now]]=bit;
    val[now][cnt[now]]=num;
}
inline LL update(LL num){
    LL belong[maxn];
    memset(belong,0,sizeof(belong));
    LL sum=0;
    for(LL i=1;i<=n;++i)
        if(s[i]){
            if(belong[s[i]])
                s[i]=belong[s[i]];
            else
                s[i]=belong[s[i]]=++sum;
        }
    LL bit=0;
    for(LL i=1;i<=n;++i)
        bit+=(s[i]<<inc[i-1]);
    if(sum==1)
        ans=max(ans,num);
    return bit;
}
inline void get_bitset(LL bit){
    for(LL i=1;i<=n;++i)
        s[i]=(bit>>inc[i-1])%8;
}
inline void solve(){
    insert(0,0);
    for(LL i=1;i<=n;++i){
        for(LL j=1;j<=n;++j){
            swap(now,last);
            cnt[now]=0;
            memset(head,0,sizeof(head));
            for(LL k=1;k<=cnt[last];++k){
                get_bitset(que[last][k]);
                LL b1=s[j-1],b2=s[j];
                LL num=val[last][k];

                LL sum=0;
                s[j]=0;
                for(LL l=1;l<=n;++l)
                    if(s[l]==b2)
                        ++sum;
                if(!b2 || sum)
                    insert(update(num),num);

                num+=a[i][j];
                get_bitset(que[last][k]);
                if(!b1&&!b2)
                    s[j]=7;
                else{
                    s[j]=max(b1,b2);
                    for(LL l=1;l<=n;++l)
                        if(s[l]&&s[l]==min(b1,b2))
                            s[l]=max(b1,b2);
                }
                insert(update(num),num);
            }
        }
    }
}
int main(){
    for(LL i=1;i<=10;++i)
        inc[i]=i*3;
    scanf("%lld",&n);
    for(LL i=1;i<=n;++i)
        for(LL j=1;j<=n;++j)
            scanf("%lld",&a[i][j]);
    solve();
    printf("%lld",ans);
    return 0;
}

P3190 [HNOI2007]神奇游乐园

题目大意

n*m的带权方格，求最大权回路 2<=n<=100，2<=m<=6

和模板题差不多，在insert时加一个最大值，自己写一遍吧，相信你能A掉的

核心代码：

inline void insert(LL bit,LL num){
    LL u=bit%hs+1;
    for(LL i=head[u];i;i=next[i])
        if(que[now][i]==bit){
            val[now][i]=max(val[now][i],num);
            return;
        }
    next[++cnt[now]]=head[u];
    head[u]=cnt[now];
    que[now][cnt[now]]=bit;
    val[now][cnt[now]]=num;
}

{} {}

以下这题由于斯坦纳树做法更简单，不作例题讲重点讲，稍微提怎么求方案

P4294 [WC2008]游览计划

题目大意

n*m的带权网格，求联通k个方格的最小权联通块方案（求某个方案而非方案数） n<=10 m<=10 k<=10

$w[tot]$表示此时选或不选，$pre[tot]$表示上一个点的$w$下标，方便输出方案数，在更新成功$val[now][val]$时同时更新 ### **Insert:** ```cpp inline void insert(LL y,LL pe,LL bit,LL num){ LL u=bit%hs+1; for(LL i=head[u];i;i=next[i]) if(que[now][i]==bit){ if(val[now][i]>num){ val[now][i]=num; pre[road[now][i]]=pe; w[road[now][i]]=(bit>>inc[y-1])%8; if(f) tmp=road[now][i]; } return; } next[++cnt[now]]=head[u]; head[u]=cnt[now]; que[now][cnt[now]]=bit; val[now][cnt[now]]=num; road[now][cnt[now]]=++tot; pre[tot]=pe; w[tot]=(bit>>inc[y-1])%8; if(f) tmp=tot; } ``` ## [P3272 [SCOI2011]地板](https://www.luogu.org/problemnew/show/P3272) 显然，$L$型地板：拐弯且仅拐弯一次。 发现没有，一个存在的插头只有两种状态：拐弯过和没拐弯过，因此我们这样定义插头： 0表没有插头，1表没拐过的插头，2表已经拐过的插头。$b1$代表当前点的右插头,$b2$代表当前点的下插头 那么会有下面的几种情况： $(1)$ $b1==0$ $and$ $b2==0

(2)$ $b1==0$ $and$ $b2==1

(3)$ $b1==1$ $and$ $b2==0

　 跟(2)差不多

(4)$ $b1==0$ $and$ $b2==2

1. 结束，将插头去掉，如果为终点更新答案，否则去掉插头则可

2. b2$向下延伸，$b1==2$ $ $ $b2==0

(5)$ $b1==2$ $and$ $b2==0

　 跟(4)差不多

(6)$ $b1==1$ $and$ $b2==1

1. 直接删去就好了，相当于两个没拐过的插头会和，形成L拐弯交界处

做完一个题当然得总结一下：这题虽然与前面回路的题不同，看似无从下手，但从L型的性质，考虑状态，全部考虑到，自然就A掉了

P2337 [SCOI2012]喵星人的入侵

这题深刻得体会到了插头dp的毒瘤emmm

这里在联通路径情况下，增加了特殊限制，相当于每个点的权值由周围八连通块炮台数量决定

要求最后方案最小路径最大，而可以放无限个障碍，显然，为了简化状态，我们最后留一条路径就好了

这里一种状态由什么来表示？插头，路径状态，已放炮台数量

和原来好像完全不一样了，别担心，多开几个数组存状态，把所有的状态全部考虑一遍就好了嘛

以下借鉴了dalao@ComeIntoPower的思想与代码

重点：

这里的插头状态：0空插头 1左插头 2右插头 3独立插头

独立插头不知道意思？其实之前算是已经接触过了，记不记得，在求最大联通块权，有一个新块7，差不多就是这个意思

由于起点终点只延伸一个方向，不参与括号匹配，所以单独标记为3

插头轮廓状态表示如下

棋盘轮廓状态：0障碍 1路径 3炮台，状态表示如下，故判断是提取八联通块中已确定的四块

Conn$函数为当前的纵坐标为$u$，插头状态为$st$，将插头$op$另一端改成$v

LL Conn(LL st,LL op,LL u,LL v)

nxt$函数表将当前棋盘状态换完$a

nxt(a) (stb-(yb<<bit(j+1))+((a)<<bit(j+1)))

滚动数组存三种小状态

本题状态较多，详情请看完整代码(内有注释),相信你能看懂

My complete code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define bit(x) ((x)<<1)
#define nxt(a) (stb-(yb<<bit(j+1))+((a)<<bit(j+1)))
using namespace std;
typedef long long LL;
const LL maxn=10000000;
const LL hs=299987;
LL n,m,now,last,K,ans;
LL cnt[2],val[2][maxn],que[2][maxn],nxt[maxn],stA[2][maxn],stB[2][maxn],stC[2][maxn],head[300000];
char a[30][30],tmp[30][30];
LL Hash(LL x,LL y,LL z){
    return ((((x)<<16|y)<<4|z));
}
void Add(LL x,LL y,LL z,LL w){
    LL u=Hash(x,y,z)%hs+1,h=Hash(x,y,z);
    for(LL i=head[u];i;i=nxt[i])
        if(que[now][i]==h){
            val[now][i]=max(val[now][i],w);
            return;
        }
    nxt[++cnt[now]]=head[u],
    head[u]=cnt[now],
    val[now][cnt[now]]=w,
    que[now][cnt[now]]=h,
    stA[now][cnt[now]]=x,
    stB[now][cnt[now]]=y,
    stC[now][cnt[now]]=z;
}
LL Conn(LL st,LL op,LL u,LL v){
    if(op==1){
        LL b=1;
        for(;;++u){
            LL p=(st>>bit(u))&3;
            if(p==1)
                b++;
            if(p==2)
                b--;
            if(!b)
                return st-(p<<bit(u))+(v<<bit(u));
        }
    } else {
        LL b=1;
        for(;;--u){
            LL p=(st>>bit(u))&3;
            if(p==2)
                b++;
            if(p==1)
                b--;
            if(!b)
                return st-(p<<bit(u))+(v<<bit(u));
        }
    }
}
inline void Solve(){
    now=0,last=1;
    val[now][++cnt[now]]=0;
    for(LL i=0;i<n;++i){
        for(LL j=1;j<=cnt[now];++j)
            stA[now][j]<<=2,
            stB[now][j]=(stB[now][j]-(((stB[now][j]>>bit(m+1))&3)<<bit(m+1)))<<2;

        for(LL j=0;j<m;++j){
            swap(now,last);
            memset(head,0,sizeof(head));
            cnt[now]=0;
            for(LL s=1;s<=cnt[last];++s){
                LL sta=stA[last][s],
                   stb=stB[last][s],
                   k=stC[last][s],
                   w=val[last][s];
                if(sta>=(1<<bit(m+1)))//上一行是否最后添加插头，添加则超出格限制，跳过 
                    continue;
                LL b1,b2,xb,yb,zb,pb;
                b1=sta>>bit(j)&3,
                b2=sta>>bit(j+1)&3;

                xb=stb>>bit(j)&3,
                yb=stb>>bit(j+1)&3;
                zb=stb>>bit(j+2)&3,
                pb=stb>>bit(j+3)&3;

                LL nsta=sta-(b1<<bit(j))-(b2<<bit(j+1));
                if((xb==1&&!b1)||(zb==1&&!b2)){//不走就拦 
                    if(!b1&&!b2){
                        Add(sta,nxt(0),k,w);//障碍 
                        w+=(xb==1)+(yb==1)+(zb==1)+(pb==1);
                        if(k<K&&a[i][j]=='.')
                            Add(sta,nxt(3),k+1,w);//炮台 
                    }
                }else if(a[i][j]=='#'){
                    if(!b1&&!b2)
                        Add(nsta,nxt(0),k,w);
                }else if(a[i][j]=='.'){
                    LL w1=w+(xb==1)+(yb==1)+(zb==1)+(pb==1),
                       w2=w;
                    w+=(xb==3)+(yb==3)+(zb==3)+(pb==3);
                    if(!b1&&!b2){
                        if(k<K)
                            Add(nsta,nxt(3),k+1,w1);//记录对走过的路径造成的影响 
                        Add(nsta+(1<<bit(j))+(2<<bit(j+1)),nxt(1),k,w);//加两个插头 
                        Add(nsta,nxt(0),k,w2);//不走 
                    }else if(!b1){// 延伸 
                        Add(nsta+(b2<<bit(j)),nxt(1),k,w);
                        Add(nsta+(b2<<bit(j+1)),nxt(1),k,w);
                    }else if(!b2){//延伸 
                        Add(nsta+(b1<<bit(j)),nxt(1),k,w);
                        Add(nsta+(b1<<bit(j+1)),nxt(1),k,w);
                    }else if(b1==2&&b2==1){//合并 
                        Add(nsta,nxt(1),k,w);
                    }else if(b1==1&&b2==1){//找到右替换成左 
                        Add(Conn(nsta,1,j,1),nxt(1),k,w);
                    }else if(b1==2&&b2==2){//找到左替换成右 
                        Add(Conn(nsta,2,j,2),nxt(1),k,w);
                    }else if(b1==3&&b2==1){//找到右替换成独立 
                        Add(Conn(nsta,1,j,3),nxt(1),k,w);
                    }else if(b1==3&&b2==2){//找到左替换成独立 
                        Add(Conn(nsta,2,j,3),nxt(1),k,w);
                    }else if(b1==1&&b2==3){//找到右替换成独立 
                        Add(Conn(nsta,1,j,3),nxt(1),k,w);
                    }else if(b1==2&&b2==3){//找到左替换成独立 
                        Add(Conn(nsta,2,j,3),nxt(1),k,w);
                    }else if(b1==3&&b2==3){//合并 
                        Add(nsta,nxt(1),k,w);
                    }
                }else if(a[i][j]=='S'||a[i][j]=='T'){
                    w+=(xb==3)+(yb==3)+(zb==3)+(pb==3);
                    if(a[i][j]=='S'&&!b1&&!b2){//起点且无插头 
                        Add(sta+(3<<bit(j)),nxt(1),k,w);
                        Add(sta+(3<<bit(j+1)),nxt(1),k,w);//延伸 
                    }else if(a[i][j]=='T'&&!b1&&!b2){//终点且无插头 
                        Add(sta+(3<<bit(j)),nxt(1),k,w);
                        Add(sta+(3<<bit(j+1)),nxt(1),k,w);//延伸 
                    }else if(!b1&&b2!=3&&b2!=0){//有非独立插头改成独立插头 
                        Add(Conn(nsta,b2,j,3),nxt(1),k,w);
                    }else if(!b2&&b1!=3&&b1!=0){//有非独立插头改成独立插头 
                        Add(Conn(nsta,b1,j,3),nxt(1),k,w);
                    }else if(!b1&&b2==3){//两端已连接，不需要再添加
                        Add(nsta,nxt(1),k,w);
                    }else if(b1==3&&!b2){////两端已连接，不需要再添加 
                        Add(nsta,nxt(1),k,w);
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&K);
    for(LL i=0;i<n;++i)
        scanf(" %s",tmp[i]);
    if(n<m){
        for(LL i=0;i<n;++i)
            for(LL j=0;j<m;++j)
                a[j][i]=tmp[i][j];
        swap(n,m);
    }else{
        for(LL i=0;i<n;++i)
            for(LL j=0;j<m;++j)
                a[i][j]=tmp[i][j];
    }
    Solve();
    for(LL i=1;i<=cnt[now];++i)
        if(!stA[now][i])
            ans=max(ans,val[now][i]);
    printf("%lld\n",ans);
    return 0;
}