Language: C++

//const int F = 10001;
//void _(){
//    int n,m;
//    cin >> n >> m;
//    vs grid(n);
//    cin >> grid;
//    MaxFlow mf;
//    rep(i,0,n-1)
//        rep(j,0,m-1){
//            if(grid[i][j] == '.') continue;
//            mf.add_edge(i*m+j,i*m+j+n*m,1);
//            rep(k,0,n-1){
//                if(grid[i][j] == '.') continue;
//                mf.add_edge(i*m+j+n*m,k*m+j,F);
//            }
//            rep(k,0,m-1){
//                if(grid[i][j] == '.') continue;
//                mf.add_edge(i*m+j+n*m,i*m+k,F);
//            }
//            if(grid[i][j] == 'S')
//                mf.add_edge(mf.source,i*m+j+n*m,F);
//            if(grid[i][j] == 'T')
//                mf.add_edge(i*m+j,mf.sink,F);
//        }
//    int flow = mf.max_flow();
//    if(flow >= F)
//        print(-1);
//    else
//        print(flow);
//}
//
#include <numeric>
#include <iomanip>
#include <algorithm>
#include <memory>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_INT(i,l,r) for(int i = l; i <= r; ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 vector<T> unique(vector<T>& arr){
    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
    return arr;
}
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
T1 void print(T x, string end = "\n"){
    cout << x << end;
}
template <typename COST_TYPE = ll>
struct MaxFlow{
    const ll FLOW_INF = 1e18;
    bool needs_prep;
    struct FlowTracker{
        ll *cap, *rcap;
        shared_ptr<ll> flow;
        bool dir;
        FlowTracker(){
            dir = 0;
            cap = rcap = NULL;
        }
        FlowTracker(ll *_cap, ll *_rcap, shared_ptr<ll> _flow, int _dir)
            :cap(_cap), rcap(_rcap), flow(_flow), dir(_dir){
            }
        ll rem()const{
            if(dir == 0){
                return *cap - *flow;
            }else{
                return *rcap + *flow;
            }
        }
        void add_flow(ll f){
            if(dir == 0)
                *flow += f;
            else
                *flow -= f;
            assert(*flow <= *cap);
            assert(-*flow <= *rcap);
        }
        operator ll()const{
            return rem();
        }
        void clear(){
            *flow = 0;
        }
        void operator-=(ll x){
            add_flow(x);
        }
        void operator+=(ll x){
            add_flow(-x);
        }
    };
    struct Edge{
        int u, v;
        ll c, rc;
        COST_TYPE cost;
        FlowTracker flow;
        Edge(){}
        Edge(int _u, int _v, ll _c, COST_TYPE _cost = 0)
            :u(_u), v(_v), c(_c), cost(_cost){
                rc = 0;
            }
        void change_cap(ll _c, ll _rc = 0){
            c = _c;
            rc = _rc;
        }
    };
    int source, sink, rt_source, rt_sink;
    MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
        needs_prep = true;
    }
    vector<vector<int>> adj;
    vector<vector<COST_TYPE>> cost;
    vector<vector<FlowTracker>> cap;
    vector<Edge> edges;
    int add_edge(int u, int v, ll c, COST_TYPE cost = 0){
        needs_prep = true;
        edges.push_back(Edge(u, v, c, cost));
        return sz(edges) - 1;
    }
    vector<int> now, lvl;
    vector<COST_TYPE> pot;
    vi indices;
    void prep(){
        if(!needs_prep){
            for(auto &_ : edges)
                _.flow.clear();
            return;
        }
        needs_prep = false;
        indices = vi{source,sink};
        for(auto& edge : edges){
            indices.push_back(edge.u);
            indices.push_back(edge.v);
        }
        sort(indices.begin(), indices.end());
        indices.erase(unique(indices.begin(), indices.end()), indices.end());
        rt_source = lower_bound(indices.begin(), indices.end(), source) - indices.begin();
        rt_sink = lower_bound(indices.begin(), indices.end(), sink) - indices.begin();
        adj.clear();
        cost.clear();
        cap.clear();
        now.clear();
        lvl.clear();
        pot.clear();
        int max_id = sz(indices) - 1;
        adj.resize(max_id + 1);
        cost.resize(max_id + 1);
        cap.resize(max_id + 1);
        now.resize(max_id + 1);
        lvl.resize(max_id + 1);
        pot.resize(max_id + 1);
        vi ordering(sz(edges));
        iota(all(ordering),0);
        random_shuffle(all(ordering));
        for(int id : ordering){
            auto &edge = edges[id];
            int u = lower_bound(indices.begin(), indices.end(), edge.u) - indices.begin();
            int v = lower_bound(indices.begin(), indices.end(), edge.v) - indices.begin();
            auto flow = make_shared<ll>(0);
            adj[u].push_back(v);
            cost[u].push_back(edge.cost);
            cap[u].push_back(FlowTracker(&edge.c, &edge.rc, flow, 0));
            if(u != v){
                adj[v].push_back(u);
                cost[v].push_back(-edge.cost);
                cap[v].push_back(FlowTracker(&edge.c, &edge.rc, flow, 1));
            }
            assert(cap[u].back() == edge.c);
            edge.flow = cap[v].back();
        }
    }
    int get_name(int x){
        auto it = lower_bound(all(indices),x);
        if(it == indices.end() || *it != x){
            indices.pb(x);
            unique(indices);
            needs_prep = true;
            it = lower_bound(all(indices),x);
        }
        assert(*it == x);
        return it-indices.begin();
    }
    void set_source(int _source){
        if(source == _source) return;
        source = _source;
        rt_source = get_name(source);
    }
    void set_sink(int _sink){
        if(sink == _sink) return;
        sink = _sink;
        rt_sink = get_name(sink);
    }
    bool dinic_bfs(){
        fill(now.begin(), now.end(), 0);
        fill(lvl.begin(), lvl.end(), 0);
        lvl[rt_source] = 1;
        vector<int> bfs(1, rt_source);
        for(int i = 0; i < sz(bfs); ++i){
            int u = bfs[i];
            for(int j = 0; j < sz(adj[u]); ++j){
                int v = adj[u][j];
                if(cap[u][j] > 0 && lvl[v] == 0){
                    lvl[v] = lvl[u] + 1;
                    bfs.push_back(v);
                }
            }
        }
        return lvl[rt_sink] > 0;
    }
    ll dinic_dfs(int u, ll flow){
        if(u == rt_sink)
            return flow;
        while(now[u] < sz(adj[u])){
            int v = adj[u][now[u]];
            if(lvl[v] == lvl[u] + 1 && cap[u][now[u]] != 0){
                ll res = dinic_dfs(v, min(flow, (ll)cap[u][now[u]]));
                if(res > 0){
                    cap[u][now[u]] -= res;
                    return res;
                }
            }
            ++now[u];
        }
        return 0;
    }
    ll max_flow(int _source, int _sink){
        set_source(_source);
        set_sink(_sink);
        prep();
        ll ans = 0;
        while(dinic_bfs()){
            ll cur = 0;
            do{
                cur = dinic_dfs(rt_source, FLOW_INF);
                ans += cur;
            }while(cur > 0);
        }
        return ans;
    }
    ll max_flow(){
        return max_flow(source, sink);
    }
};
const int F = 10001;
void _(){
    int n,m;
    cin >> n >> m;
    vs grid(n);
    cin >> grid;
    MaxFlow mf;
    rep(i,0,n-1)
        rep(j,0,m-1){
            if(grid[i][j] == '.') continue;
            mf.add_edge(i*m+j,i*m+j+n*m,1);
            rep(k,0,n-1){
                if(grid[i][j] == '.') continue;
                mf.add_edge(i*m+j+n*m,k*m+j,F);
            }
            rep(k,0,m-1){
                if(grid[i][j] == '.') continue;
                mf.add_edge(i*m+j+n*m,i*m+k,F);
            }
            if(grid[i][j] == 'S')
                mf.add_edge(mf.source,i*m+j+n*m,F);
            if(grid[i][j] == 'T')
                mf.add_edge(i*m+j,mf.sink,F);
        }
    int flow = mf.max_flow();
    if(flow >= F)
        print(-1);
    else
        print(flow);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        _();
}


Compiler output:
a.cc:129:27: error: 'numeric_limits' was not declared in this scope
  129 |     MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
      |                           ^~~~~~~~~~~~~~
a.cc:129:42: error: expected primary-expression before 'int'
  129 |     MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
      |                                          ^~~
a.cc:129:67: error: 'numeric_limits' was not declared in this scope
  129 |     MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
      |                                                                   ^~~~~~~~~~~~~~
a.cc:129:82: error: expected primary-expression before 'int'
  129 |     MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
      |                                                                                  ^~~
a.cc: In member function 'void MaxFlow<COST_TYPE>::prep()':
a.cc:175:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  175 |         random_shuffle(all(ordering));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:34:
/usr/include/c++/14/bits/stl_algo.h:4492:5: note: declared here
 4492 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
a.cc: In instantiation of 'void MaxFlow<COST_TYPE>::prep() [with COST_TYPE = long long int]':
a.cc:250:9:   required from 'll MaxFlow<COST_TYPE>::max_flow(int, int) [with COST_TYPE = long long int; ll = long long int]'
  250 |         prep();
      |         ^~~~
a.cc:262:24:   required from 'll MaxFlow<COST_TYPE>::max_flow() [with COST_TYPE = long long int; ll = long long int]'
  262 |         return max_flow(source, sink);
      |                ~~~~~~~~^~~~~~~~~~~~~~
a.cc:289:27:   required from here
  289 |     int flow = mf.max_flow();
      |                ~~~~~~~~~~~^~
a.cc:175:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  175 |         random_shuffle(all(ordering));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4492:5: note: declared here
 4492 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
a.cc:175:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  175 |         random_shuffle(all(ordering));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4492:5: note: declared here
 4492 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~