最小割的裸题。先拆点。之后暴力边可过，但更好的方法是每行每列建虚点，每片莲叶像所在行列互相连边。然后跑最大流就好。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,bx,by,ex,ey,s,t,cnt,tot,id[105][105],head[100005],dep[100005],to[1000005],nxt[1000005],dd[1000005];
char str[105][105];
queue<int> q;
void adde(int u,int v,int d){
to[++cnt]=v;
nxt[cnt]=head[u];
dd[cnt]=d;
head[u]=cnt;
to[++cnt]=u;
nxt[cnt]=head[v];
dd[cnt]=0;
head[v]=cnt;
}
bool bfs(){
for(int i=s;i<=t;i++){
dep[i]=0;
}
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front(),v;
q.pop();
for(int i=head[u];i;i=nxt[i]){
v=to[i];
if(dd[i]&&!dep[v]){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int f){
if(u==t||!f){
return f;
}
int v,tmp,flow=0;
for(int i=head[u];i&&f;i=nxt[i]){
v=to[i];
if(dd[i]&&dep[v]==dep[u]+1&&(tmp=dfs(v,min(f,dd[i])))){
dd[i]-=tmp;
dd[i^1]+=tmp;
f-=tmp;
flow+=tmp;
}
}
if(!flow){
dep[u]=0;
}
return flow;
}
int maxflow(){
int flow=0;
while(bfs()){
flow+=dfs(s,inf);
}
if(flow>=inf){
puts("-1");
exit(0);
}
return flow;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",str[i]+1);
for(int j=1;j<=m;j++){
if(str[i][j]=='S'){
bx=i;
by=j;
}else if(str[i][j]=='T'){
ex=i;
ey=j;
}else if(str[i][j]=='o'){
tot++;
id[i][j]=n+m+tot;
}
}
}
if(bx==ex||by==ey){
puts("-1");
return 0;
}
s=0,t=n+m+2*tot+1,cnt=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str[i][j]=='o'){
adde(id[i][j],id[i][j]+tot,1);
adde(id[i][j]+tot,i,inf);
adde(i,id[i][j],inf);
adde(id[i][j]+tot,j+n,inf);
adde(j+n,id[i][j],inf);
}
}
}
adde(s,bx,inf);
adde(s,by+n,inf);
adde(ex,t,inf);
adde(ey+n,t,inf);
printf("%d
",maxflow());
return 0;
}