题解

#include<bits/stdc++.h>
using namespace std;
const int fni=0xc0c0c0c0;
int n,m,p,hs[2100000],sta[50000],cnt,res;
void pr(int x){for(int i=0;i<=m;i++)printf("%d",(x>>i*3)&7);}
int f[2][16][50000];
//0:block 1:left plug 2:right plug 3:part of the route 4:free plug 5:cannon 6:bi-direction plug
//0&5 are 'insulated',which do not act with any state.
//3 is 'inert',which cannot expand.
//6 is 'hyperactive',which has the necessity of expanding in both directions.
//4 is 'parasitic',which need a 1/2 plug to produce, otherwise it is as difficult as 6 when to be produced.
//1&2 are 'mundane',which do not have strong characteristics.
//all plugs except the 'insulated' 0&5 and the 'inert' 3, once put above, will always expand.
char s[30][30];
int num[30];
void dfs1(int pos,int msk,int fre,int tms){
	if(pos==m+1){
		if(tms)return;
		for(int i=1;i<pos;i++){
			if((num[i]==1||num[i]==2||num[i]==4)&&num[i-1]==3&&num[i+1]==3)return;
			if(num[i]==6&&(num[i-1]==3||num[i+1]==3))return;
		}
		cnt++,hs[msk]=cnt,sta[cnt]=msk;
		return;
	}
	num[pos]=0;dfs1(pos+1,msk,fre,tms);
	num[pos]=3,dfs1(pos+1,msk+(3<<pos*3),fre,tms);
	num[pos]=5;dfs1(pos+1,msk+(5<<pos*3),fre,tms);
	if(!pos||num[pos-1]==0||num[pos-1]==5){
		num[pos]=1,dfs1(pos+1,msk+(1<<pos*3),fre,tms+1);
		num[pos]=6,dfs1(pos+1,msk+(6<<pos*3),fre,tms);
	}
	if(!pos||(num[pos-1]!=2&&num[pos-1]!=6&&num[pos-1]!=4))num[pos]=2,dfs1(pos+1,msk+(2<<pos*3),fre,tms-1);
	if((!pos||num[pos-1]==0||num[pos-1]==5||num[pos-1]==3)&&fre<2)num[pos]=4,dfs1(pos+1,msk+(4<<pos*3),fre+1,tms);
}
int nex(int y,int k){
	if(y==m-1){
		int L=k>>m*3;k-=(L<<m*3);
		if(L!=0&&L!=3&&L!=5)return 0;
		return hs[k<<3];
	}
	return hs[k];
}
int P=0,Q=1;
void chmx(int j,int w,int id,int nw,int K,int bon=0){
	int nid=nex(j,K);
//	printf("%d:",nid),pr(K),puts("");
	if(nid&&nw<=p)f[Q][nw][nid]=max(f[Q][nw][nid],f[P][w][id]+bon);
}
int nex2(int y,int K){
	for(int i=y,j=0;i<=m;i++){
		if(((K>>i*3)&7)==1)j++;
		if(((K>>i*3)&7)==2&&!j--)return i;
	}
}
int las1(int y,int K){
	for(int i=y,j=0;i>=0;i--){
		if(((K>>i*3)&7)==2)j++;
		if(((K>>i*3)&7)==1&&!j--)return i;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=0;i<n;i++)scanf("%s",s[i]);
	if(n<m){
		for(int i=0;i<n;i++)for(int j=i+1;j<m;j++)swap(s[i][j],s[j][i]);
		swap(n,m); 
	}
	dfs1(0,0,0,0);
//	printf("%d\n",cnt);
//	for(int i=1;i<=cnt;i++)pr(sta[i]),puts("");
	memset(f[P],fni,sizeof(f[P]));
	f[P][0][hs[0]]=0;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++,P^=1,Q^=1){
		memset(f[Q],fni,sizeof(f[Q]));
		for(int w=0;w<=p;w++)for(int id=1;id<=cnt;id++){
			if(f[P][w][id]<0)continue;
			int k=sta[id];
//			printf("(%d,%d)[%d,%d]",i,j,w,id);pr(k);printf(":%d\n",f[P][w][id]);
			int H=0,Y=(k>>j*3)&7,U=(k>>(j+1)*3)&7,I=(k>>(j+2)*3)&7;
			if(U==6)continue;
			//impossible to have 6 above, as 'hyperactive' 6 is 'hyper', will immediately fission into 1&2.
			int K=k-(Y<<j*3),KHU=K;
			K-=(U<<(j+1)*3);int KH=K;
			if(j)H=((k>>(j-1)*3)&7),K-=(H<<(j-1)*3);
			int bon=(H==5)+(Y==5)+(U==5)+(I==5);
			int nob=(H!=0&&H!=5)+(Y!=0&&Y!=5)+(U!=0&&U!=5)+(I!=0&&I!=5);
			if((H==0||H==5)&&(U==0||U==5)&&s[i][j]!='#'){
				//situation of producing 'hyperactive' 6 and 'parasitic' 4(when it does not parasitize)
				if(s[i][j]=='S'||s[i][j]=='T')chmx(j,w,id,w,KHU+(4<<j*3),bon);
				else chmx(j,w,id,w,KHU+(6<<j*3),bon);
			}
			if(H!=6&&(U==0||U==5||U==3)&&s[i][j]!='S'&&s[i][j]!='T'){
				//situation where it is possible to put 'insulated' 0&5 in.
				chmx(j,w,id,w,KHU);//putting 0.
				if(s[i][j]!='#')chmx(j,w,id,w+1,KHU+(5<<j*3),nob);//putting 5.
			}
			if(s[i][j]=='#')continue;//the only operation under this circumstance is putting 0.
			if(U!=0&&U!=5&&U!=3){//situation when U has to expand.
				if(H!=0&&H!=5){//two plugs meet.
					if(s[i][j]=='S'||s[i][j]=='T')continue;//there can't be two different routes around endpoints.
					if(H==3)continue;//H has been on a complete route.
					if(Y!=0&&Y!=5)continue;//a 'cancer' forms, which is invalid. 
					if(H==1&&U==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)-(1<<nex2(j,K)*3),bon);
					//two 1s will 'alpha-fusion', turing a 2 into 1, and leaving three 3s. 
					if(H==1&&U==2)continue;//1&2 will 'circle', which is invalid.
					if(H==2&&U==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
					//2&1 will 'beta-fusion',only leaving three 3s. 
					if(H==2&&U==2)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(1<<las1(j,K)*3),bon);
					//two 2s will 'gamma-fusion', turing an 1 into 2, and leaving three 3s.
					if(H==6&&U==1)chmx(j,w,id,w,K+(1<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
					if(H==6&&U==2)chmx(j,w,id,w,K+(2<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
					//6 shall be seen as 1+2.
					if(H==4&&U==4){chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);continue;}
					//two 'parasitic' 4, forming a complete route.
					if(H==4&&U==1||H==1&&U==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(2<<nex2(j,K)*3),bon);
					if(H==4&&U==2||H==2&&U==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(3<<las1(j,K)*3),bon);
					if(H==6&&U==4)chmx(j,w,id,w,K+(4<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
					//4 going parasitize. 
					continue;
				}
				if(s[i][j]=='S'||s[i][j]=='T'){
					if(U==1)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3)+(2<<nex2(j,K)*3),bon);
					if(U==2)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3)+(3<<las1(j,K)*3),bon);
					if(U==4)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3),bon);
					continue;
				}
				chmx(j,w,id,w,KH+(U<<j*3)+(3<<(j+1)*3),bon);
				continue;
			}
			if(H!=0&&H!=5&&H!=3){
				if(U==3)continue;
				if(s[i][j]=='S'||s[i][j]=='T'){
					if(H==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(2<<nex2(j,K)*3)+(U<<(j+1)*3),bon);
					if(H==2)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<las1(j,K)*3)+(U<<(j+1)*3),bon);
					if(H==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(U<<(j+1)*3),bon);
					if(H==6)chmx(j,w,id,w,K+(4<<(j-1)*3)+(3<<j*3)+(U<<(j+1)*3),bon);
					continue;
				}
				if(H==1||H==2||H==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(H<<j*3)+(U<<(j+1)*3),bon);
				else chmx(j,w,id,w,K+(1<<(j-1)*3)+(2<<j*3)+(U<<(j+1)*3),bon);
			}
		}
	}
	for(int j=1;j<=cnt;j++){
		bool ok=true;
		int k=sta[j];
		for(int t=0;t<=m;t++)if(((k>>t*3)&7)!=0&&((k>>t*3)&7)!=3&&((k>>t*3)&7)!=5){ok=false;break;}
		if(!ok)continue;
		for(int i=0;i<=p;i++)res=max(res,f[P][i][j]);
	}
	printf("%d\n",res);
	return 0;
}