插头dp小结
插头dp:
\(A:\)插头dp是什么？
\(B:\)一种基于连通性状态压缩的动态规划问题
\(A:\)请问有什么应用呢？
\(B:\)各种网格覆盖问题，范围允许状压解决，常用于计算方案数与联通块权值
\(A:\)轮廓线与插头呢？？？
\(B:\)轮廓线是状压的部分，用于解决插头的情况，不同于常见的状压dp，为了更好地处理状态，通常要要到括号表示法、最小表示法等，插头是格与格中的转移，可理解成将拼图连接的位置
\(A:\)本文将讲解哪些类型的题目呢？
\(B:\)单回路覆盖方案数，多回路覆盖方案数，骨牌覆盖，联通块最大权，单回路最大权，最小联通块方案，特殊型覆盖，多种限制的最大权
\(A:\)那我们开始吧！！
各种例题：
ps：以下的图都并非唯一状态，基于让读者更好理解采用最经典的图例
模板： P5056 【模板】插头dp
题目大意
给出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\)
当前点能走(非障碍必须走)
\((1)\) \(!b1\) \(and\) \(!b2\)，则要加两个插头(一个左插头，一个有插头)，确保该点走过
\((2)\) \(!b1\) \(and\) \(b2\)只有一个插头，该插头向下延伸，选择直走或往右拐，等同于延续一个连通分量
此时插头的括号状态不变，通俗地说，就是插头本来是几转移后也是几
注意，插头在轮廓线上的位置变了，如果直走\(b2\)的位置为\(0\)，\(b1\)为原来的\(b2\)
\((3)\) \(b1\) \(and\) \(!b2\)则向右延伸，直走或向下拐，与\((2)\)同理
\((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)\)
\((7)\) \(b1==1\) \(and\) \(b2==2\)出现这种状态，达到了最终闭合状态，当前点为终点更新答案，否则状态不合法
本题利用\(hash\)和滚动节省空间，为方便与快捷用位运算实现四进制，具体细节看代码，
或许你看到每行之间多了一个这样的状态转移，在此提一下，相当于到每行第一个格子时，前面补一个空插头，剩下的部分从上一行最后一个格子那里直接搬过来
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
这里不需要形成回路，而是经典的联通块题，上面的方法无用武之地了(判断联通)，通常我们采取最小表示法
\(n<=9\)用\(8\)进制(与四进制同理)表示，同一个联通块用相同数字表示，数字也只是暂时的而已，选择一个块后，由于可能会改变联通状态，要重新标记数字
此题的轮廓线有所不同，因为两相邻块均选是直接联通的，如下图
每个方格有两种基本状态
不选
当然得考虑状态合理，无下插头或下插头所在联通块还有其他插头，否则下插头被孤立而不形成联通块了
大家发现没有？
这里每个状态仅合理而已，并不能确定这是可取的最终状态，因为最后得保证只有一个联通块(其实上文也)，详细请看\(update\)
那为什么不考虑右插头呢？而要判断下插头呢？
因为下插头以后再也不会判断了，所以要考虑状态合理，右插头到下一行自然会考虑状态
右插头来自上一个转移状态，很可能形成新块\(7\)，故这样转移条件会变得严苛，最终答案通常会小于正确答案
选
\((1)\) \(!b1\) \(and\) \(!b2\)单独形成新块，此块命名为7
\((2)\) \(b1\) \(or\) \(b2\) 此块与插头相连，更新联通块状态，这就是伟大的最小表示法
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
\(road[now][bit]=\)++\(tot\)表示\(val[now][val]\)最小时的状态，和\(val\)与\(que\)一样是滚动数组，因为之后就不需要了
\(w[tot]\)表示此时选或不选，\(pre[tot]\)表示上一个点的\(w\)下标，方便输出方案数，在更新成功\(val[now][val]\)时同时更新
Insert:
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]地板
显然，\(L\)型地板：拐弯且仅拐弯一次。
发现没有，一个存在的插头只有两种状态：拐弯过和没拐弯过，因此我们这样定义插头：
0表没有插头，1表没拐过的插头，2表已经拐过的插头。\(b1\)代表当前点的右插头,\(b2\)代表当前点的下插头
那么会有下面的几种情况：
\((1)\) \(b1==0\) \(and\) \(b2==0\)
-
\(b1\)添加一个插头\(1\)，相当于加入一个从该点出发向下的\(L\)地板
-
\(b2\)添加一个插头\(1\)，相当于加入一个从该点出发向右的\(L\)地板
-
\(b1\),\(b2\)均改成插头\(2\)，相当于该点作为\(L\)地板的拐弯处
\((2)\) \(b1==0\) \(and\) \(b2==1\)
-
\(b1=1\),\(b2=0\) 相当于继续直走，不拐弯，所以\(b1\)转为\(b2\)，\(b2\)此时无插头了
-
\(b1=0\),\(b2=2\) 相当于向右拐
\((3)\) \(b1==1\) \(and\) \(b2==0\)
跟\((2)\)差不多
\((4)\) \(b1==0\) \(and\) \(b2==2\)
-
结束，将插头去掉，如果为终点更新答案，否则去掉插头则可
-
\(b2\)向下延伸，\(b1==2\) $ $ \(b2==0\)
\((5)\) \(b1==2\) \(and\) \(b2==0\)
跟\((4)\)差不多
\((6)\) \(b1==1\) \(and\) \(b2==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;
}