Problem:
 Score : 800 points    Problem Statement There is a pond with a rectangular shape.
The pond is divided into a grid with H rows and W columns of squares.
We will denote the square at the i -th row from the top and j -th column from the left by (i,\ j) .  Some of the squares in the pond contains a lotus leaf floating on the water.
On one of those leaves, S , there is a frog trying to get to another leaf T .
The state of square (i,\ j) is given to you by a character a_{ij} , as follows:   . : A square without a leaf.  o : A square with a leaf floating on the water.  S : A square with the leaf S .  T : A square with the leaf T .   The frog will repeatedly perform the following action to get to the leaf T : "jump to a leaf that is in the same row or the same column as the leaf where the frog is currently located."  Snuke is trying to remove some of the leaves, other than S and T , so that the frog cannot get to the leaf T .
Determine whether this objective is achievable. If it is achievable, find the minimum necessary number of leaves to remove.      Constraints  2 ≤ H, W ≤ 100  a_{ij} is . , o , S or T .  There is exactly one S among a_{ij} .  There is exactly one T among a_{ij} .         Input Input is given from Standard Input in the following format:  H  W  a_{11}  ...  a_{1W}  :  a_{H1}  ...  a_{HW}       Output If the objective is achievable, print the minimum necessary number of leaves to remove.
Otherwise, print -1 instead.        Sample Input 1 3 3
S.o
.o.
o.T      Sample Output 1 2  Remove the upper-right and lower-left leaves.       Sample Input 2 3 4
S...
.oo.
...T      Sample Output 2 0       Sample Input 3 4 3
.S.
.o.
.o.
.T.      Sample Output 3 -1       Sample Input 4 10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo      Sample Output 4 5

Solution (Python):
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class Dinic():
    def __init__(self, n, s, t):
        self.n, self.s, self.t = n, s, t
        self.to = defaultdict(list)
        self.level = [-1]
        self.max_flow = -1

    def add_edge(self, u, v, cap):
        u_index_in_to_v = len(self.to[v])
        v_index_in_to_u = len(self.to[u])
        self.to[u].append([v, cap, u_index_in_to_v])
        self.to[v].append([u, 0, v_index_in_to_u])

    
    def add_undir_edge(self, u, v, cap):
        u_index_in_to_v = len(self.to[v])
        v_index_in_to_u = len(self.to[u])
        self.to[u].append([v, cap, u_index_in_to_v])
        self.to[v].append([u, cap, v_index_in_to_u])

    def set_level(self):
        s = self.s
        level = [-1] * self.n
        level[s] = 0
        q = deque()
        q.append([s, 0])
        while q:
            u, u_level = q.popleft()
            for v, cap, _ in self.to[u]:
                if cap == 0: continue
                if level[v] != -1: continue
                level[v] = u_level + 1
                if v == self.t:
                    self.level = level
                    return True
                q.append([v, u_level + 1])
        return False

    def dfs(self, u=-1, flow_to_me=10 ** 16):
        if u == -1: u = self.s
        if u == self.t: return flow_to_me
        flow_from_me = 0
        u_level = self.level[u]
        for utov_i, (v, cap, vtou_i) in enumerate(self.to[u]):
            if self.level[v] != u_level + 1: continue
            if cap == 0: continue
            flow_to_v = self.dfs(v, min(cap, flow_to_me - flow_from_me))
            if not flow_to_v: continue
            flow_from_me += flow_to_v
            self.to[u][utov_i][1] -= flow_to_v
            self.to[v][vtou_i][1] += flow_to_v
        return flow_from_me

    def calculation(self):
        res = 0
        while self.set_level():
            res += self.dfs()
        return res

    
    def get_max_flow(self):
        if self.max_flow == -1:
            self.max_flow = self.calculation()
        return self.max_flow

h,w=MI()
aa=[input() for _ in range(h)]

def main():
    inf=10**9+7
    s=h+w
    t=h+w+1
    mc=Dinic(h+w+2,s,t)
    si,sj,ti,tj=-1,-2,-3,-4
    for i,row in enumerate(aa):
        for j,a in enumerate(row):
            if a=="S":
                if i==ti or j==tj:
                    print(-1)
                    exit()
                si,sj=i,j
                mc.add_edge(s,i,inf)
                mc.add_edge(s,j+h,inf)
            elif a=="T":
                if i==si or j==sj:
                    print(-1)
                    exit()
                ti,tj=i,j
                mc.add_edge(i,t,inf)
                mc.add_edge(j+h,t,inf)
            elif a=="o":
                mc.add_undir_edge(i,j+h,1)
    print(mc.get_max_flow())

main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def FF(E, s, t):
    NN = H+W+2
    G = [[] for _ in range(NN)]
    for a, b, f in E:
        G[a].append([b, f, len(G[b])])
        G[b].append([a, 0, len(G[a])-1])
    
    def dfs(s, t, f):
        if s == t:
            return f
        used[s] = 1
        for i, (b, _f, r) in enumerate(G[s]):
            if used[b] or _f == 0: continue
            d = dfs(b, t, min(f, _f))
            if d > 0:
                G[s][i][1] -= d
                G[b][r][1] += d
                return d
        return 0
    
    flow = 0
    while 1:
        used = [0] * NN
        f = dfs(s, t, 10**100)
        if f == 0:
            return flow
        flow += f

E = []

H, W = map(int, input().split())
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == "o":
            E.append((i, j+H, 1))
            E.append((j+H, i, 1))
        elif A[j] == "S":
            S = (i, j+H)
        elif A[j] == "T":
            T = (i, j+H)
E.append((H+W, S[0], 10**6))
E.append((H+W, S[1], 10**6))
E.append((T[0], H+W+1, 10**6))
E.append((T[1], H+W+1, 10**6))

ff = FF(E, H+W, H+W+1)
print(ff if ff < 10**6 else -1)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def FF(E, s, t):
    NN = H+W+2
    G = [[] for _ in range(NN)]
    for a, b, f in E:
        G[a].append([b, f, len(G[b])])
        G[b].append([a, 0, len(G[a])-1])
    
    def dfs(s, t, f):
        if s == t:
            return f
        used[s] = 1
        for i, (b, _f, r) in enumerate(G[s]):
            if used[b] or _f == 0: continue
            d = dfs(b, t, min(f, _f))
            if d > 0:
                G[s][i][1] -= d
                G[b][r][1] += d
                return d
        return 0
    
    flow = 0
    while 1:
        used = [0] * NN
        f = dfs(s, t, 10**100)
        if f == 0:
            return flow
        flow += f

E = []

H, W = map(int, input().split())
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == "o":
            E.append((i, j+H, 1))
            E.append((j+H, i, 1))
        elif A[j] == "S":
            S = (i, j+H)
        elif A[j] == "T":
            T = (i, j+H)
E.append((H+W, S[0], 10**6))
E.append((H+W, S[1], 10**6))
E.append((T[0], H+W+1, 10**6))
E.append((T[1], H+W+1, 10**6))

ff = FF(E, H+W, H+W+1)
print(ff if ff < 10**6 else -1)

Solution (Python):
import sys
input = sys.stdin.readline

from scipy.sparse.csgraph import dijkstra

H,W = map(int,input().split())






INF = 10 ** 9
start = 0
goal = H+W+1
V = H+W+2
graph = [[0] * V for _ in range(V)]
edges = [] 
for i in range(H):
    row = input()
    for j,cell in enumerate(row):
        if cell == 'o':
            graph[1+i][1+H+j] = 1
            graph[1+H+j][1+i] = 1
    s = row.find('S')
    t = row.find('T')
    if s != -1:
        graph[start][1+i] = INF
        graph[start][1+H+s] = INF
    if t != -1:
        graph[1+i][goal] = INF
        graph[1+H+t][goal] = INF



def max_flow(graph):
    f = 0
    while True:
        if f > 200:
            return -1
        dist,pred = dijkstra(graph, indices = start, unweighted = True, return_predecessors = True)
        if dist[goal] > INF:
            return f
        f += 1
        after = goal
        while after != start:
            before = pred[after]
            graph[before][after] -= 1
            graph[after][before] += 1
            after = before

answer = max_flow(graph)
print(answer)

Solution (Python):
from collections import deque
INF = 10**9

class Dinic:
    def __init__(self, n):
        self.n = n
        self.edge = [[] for _ in range(n)]
        self.level = [None] * self.n 
        self.it = [None] * self.n 

    def add_edge(self, fr, to, cap):
        
        forward = [to, cap, None]
        backward = [fr, 0, forward]
        forward[2] = backward
        self.edge[fr].append(forward)
        self.edge[to].append(backward)

    def add_bidirect_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge2 = [v1, cap2, edge1]
        edge1[2] = edge2
        self.edge[v1].append(edge1)
        self.edge[v2].append(edge2)

    
    
    def bfs(self, s, t):
        self.level = [None] * self.n
        dq = deque([s])
        self.level[s] = 0
        while dq:
            v = dq.popleft()
            lv = self.level[v] + 1
            for dest, cap, _ in self.edge[v]: 
                if cap > 0 and self.level[dest] is None:
                    self.level[dest] = lv
                    dq.append(dest)
        return self.level[t] is not None

    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.it[v]:
            to, cap, rev = e
            if cap and self.level[v] < self.level[to]:
                ret = self.dfs(to, t, min(f, cap))
                
                if ret:
                    e[1] -= ret
                    rev[1] += ret
                    return ret
        
        return 0

    def flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            for i in range(self.n):
                self.it[i] = iter(self.edge[i])
            
            f = INF
            while f > 0:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

N, M = [int(item) for item in input().split()]
n = N + M + 2
dinic = Dinic(n)
for i in range(N):
    line = input().rstrip()
    for j, ch in enumerate(line):
        if ch == ".":
            pass
        elif ch == "o":
            v1 = i + 1
            v2 = N + j + 1
            dinic.add_bidirect_edge(v1, v2, 1, 1)
        elif ch == "S":
            v1 = i + 1
            v2 = N + j + 1
            dinic.add_edge(0, v1, INF)
            dinic.add_edge(0, v2, INF)
        elif ch == "T":
            v1 = i + 1
            v2 = N + j + 1
            dinic.add_edge(v1, n-1, INF)
            dinic.add_edge(v2, n-1, INF)
ans = dinic.flow(0, n-1)
if ans >= INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import collections
import queue


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u]) - 1])
            self.edges[v].append([u, c, len(self.edges[u])])
            self.edges[u].append([v, 0, len(self.edges[v]) - 1])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.put(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


H, W = map(int, input().split())
graph = Dinic(H+W+2)

for h in range(H):
    tmp = str(input())
    for w in range(W):
        if tmp[w] == 'o':
            graph.add(h+1, H+1+w, 1)
            graph.add(H + w + 1, h + 1, 1)
        if tmp[w] == 'S':
            start = [h, w]
            graph.add(0, h+1, float('inf'))
            graph.add(0, H+w+1, float('inf'))
        if tmp[w] == 'T':
            goal = [h, w]
            graph.add(h+1, H+W+1, float('inf'))
            graph.add(H+1+w, H+W+1, float('inf'))

if start[0] == goal[0] or start[1] == goal[1]:
    print(-1)
    quit()
print(graph.maxFlow(0, H+W+1))

Solution (Python):
import itertools
import os
import sys
from collections import deque, defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
table = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

S = H + W
T = H + W + 1
graph = [[] for _ in range(H + W + 2)]
for h, w in itertools.product(range(H), range(W)):
    if table[h][w] == '.':
        continue
    if table[h][w] == 'S':
        graph[S].append((h, IINF))
        graph[S].append((H + w, IINF))
    elif table[h][w] == 'T':
        graph[h].append((T, IINF))
        graph[H + w].append((T, IINF))
    graph[h].append((H + w, 1))
    graph[H + w].append((h, 1))


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                flow = self._dfs(from_v, to_v, dist, iter)
                if flow == 0:
                    break
                ret += flow
        return ret


mf = Dinic(graph=graph).maximum_flow(S, T)
if mf >= IINF:
    print(-1)
else:
    print(mf)

Solution (Python):
from collections import deque
from itertools import combinations
class Dinic:
    def __init__(self, N):
        self.N=N
        self.G=[[]for _ in range(N)]
    def add_edge(self,fr,to,cap):
        forward=[to,cap,None]
        forward[2]=backward=[fr,0,forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)
    def add_multi_edge(self,v1,v2,cap1,cap2):
        edge1=[v2,cap1,None]
        edge1[2]=edge2=[v1,cap2,edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)
    def bfs(self,s,t):
        self.level=level=[None]*self.N
        deq=deque([s])
        level[s]=0
        G=self.G
        while deq:
            v=deq.popleft()
            lv=level[v]+1
            for w,cap,_ in G[v]:
                if cap and level[w]is None:
                    level[w]=lv
                    deq.append(w)
        return level[t]is not None
    def dfs(self,v,t,f):
        if v==t:return f
        level=self.level
        for e in self.it[v]:
            w,cap,rev=e
            if cap and level[v]<level[w]:
                d=self.dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    rev[1]+=d
                    return d
        return 0
    def flow(self,s,t):
        flow=0
        INF=10**9+7
        G=self.G
        while self.bfs(s,t):
            *self.it,=map(iter,self.G)
            f=INF
            while f:
                f=self.dfs(s,t,INF)
                flow+=f
        return flow
INF=10**9+7
t,*a=open(0)
h,w=map(int,t.split())
d=Dinic(h+w+3)
add=d.add_multi_edge
for i,s in enumerate(a,1):
    for j,t in enumerate(s[:-1],h+1):
        if t!='.':
            if t=='S':
                add(0,i,INF,INF)
                add(0,j,INF,INF)
            elif t=='T':
                add(i,h+w+2,INF,INF)
                add(j,h+w+2,INF,INF)
            add(i,j,1,1)
a=d.flow(0,h+w+2)
print(-(a>=INF)or a)

Solution (Python):
from collections import deque
from itertools import combinations
class Dinic:
    def __init__(self, N):
        self.N=N
        self.G=[[]for _ in range(N)]
    def add_edge(self,fr,to,cap):
        forward=[to,cap,None]
        forward[2]=backward=[fr,0,forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)
    def add_multi_edge(self,v1,v2,cap1,cap2):
        edge1=[v2,cap1,None]
        edge1[2]=edge2=[v1,cap2,edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)
    def bfs(self,s,t):
        self.level=level=[None]*self.N
        deq=deque([s])
        level[s]=0
        G=self.G
        while deq:
            v=deq.popleft()
            lv=level[v]+1
            for w,cap,_ in G[v]:
                if cap and level[w]is None:
                    level[w]=lv
                    deq.append(w)
        return level[t]is not None
    def dfs(self,v,t,f):
        if v==t:return f
        level=self.level
        for e in self.it[v]:
            w,cap,rev=e
            if cap and level[v]<level[w]:
                d=self.dfs(w,t,min(f,cap))
                if d:
                    e[1]-=d
                    rev[1]+=d
                    return d
        return 0
    def flow(self,s,t):
        flow=0
        INF=10**9+7
        G=self.G
        while self.bfs(s,t):
            *self.it,=map(iter,self.G)
            f=INF
            while f:
                f=self.dfs(s,t,INF)
                flow+=f
        return flow
INF=10**9+7
t,*a=open(0)
h,w=map(int,t.split())
d=Dinic(h+w+3)
add=d.add_multi_edge
for i,s in enumerate(a,1):
    for j,t in enumerate(s[:-1],h+1):
        if t!='.':
            if t=='S':
                add(0,i,INF,INF)
                add(0,j,INF,INF)
            elif t=='T':
                add(i,h+w+2,INF,INF)
                add(j,h+w+2,INF,INF)
            add(i,j,1,1)
a=d.flow(0,h+w+2)
print(-(a>=INF)or a)

Solution (Python):
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  
        
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def add_edge_undirected(self, u, v, cap):  
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, cap, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  
                    e[CAP] -= d  
                    self.V[e[TO]][e[REV]][CAP] += d  
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(s):  
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow
H, W = map(int, input().split())
dinic = Dinic(H+W+2)
for i in range(H):
    a = input()
    for j, a_ in enumerate(a):
        if a_=="S":
            start = i, j
        elif a_=="T":
            goal = i, j
        if a_!=".":
            dinic.add_edge_undirected(H + j, i, 1)
dinic.add_edge_undirected(H+W, start[0], 1<<30)
dinic.add_edge_undirected(H+W, start[1]+H, 1<<30)
dinic.add_edge_undirected(H+W+1, goal[0], 1<<30)
dinic.add_edge_undirected(H+W+1, goal[1]+H, 1<<30)

if start[0]==goal[0] or start[1]==goal[1]:
    print(-1)
else:
    print(dinic.solve(H+W, H+W+1))

Solution (Python):

import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

if __name__ =="__main__":
    H,W=map(int,input().split())
    a=[list(input()) for i in range(H)]
    Dn=Dinic(2+H+W)
    INF=10**15
    
    
    s=(-1,-1)
    t=(-1,-1)
    for i in range(H):
        for j in range(W):
            if a[i][j]!=".":
                Dn.add_edge(i+1,H+1+j,1)
                Dn.add_edge(H+1+j,i+1,1)
            if a[i][j]=="S":
                Dn.add_edge(0,i+1,INF)
                Dn.add_edge(0,H+1+j,INF)
                s=(i,j)
            if a[i][j]=="T":
                Dn.add_edge(i+1,H+W+1,INF)
                Dn.add_edge(H+1+j,H+W+1,INF)
                t=(i,j)
    if s[0]==t[0] or s[1]==t[1]:
        print(-1)
    else:
        ans=Dn.max_flow(0,1+H+W)
        print(ans)

Solution (Python):

import queue

class Dinic:
    """Implementation of Dinic's Alogorithm"""

    def __init__(self, v, inf = 1000000007):
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
                d = self.dfs(e['to'], t, min(f, e['cap']))
                if d > 0:
                    e['cap'] -= d
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            
            if self.level[t] < 0 : return flow
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf)
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

if __name__ =="__main__":
    H,W=map(int,input().split())
    a=[list(input()) for i in range(H)]
    Dn=Dinic(2+H+W)
    INF=10**15
    
    
    s=(-1,-1)
    t=(-1,-1)
    for i in range(H):
        for j in range(W):
            if a[i][j]!=".":
                Dn.add_edge(i+1,H+1+j,1)
                Dn.add_edge(H+1+j,i+1,1)
            if a[i][j]=="S":
                Dn.add_edge(0,i+1,INF)
                Dn.add_edge(0,H+1+j,INF)
                s=(i,j)
            if a[i][j]=="T":
                Dn.add_edge(i+1,H+W+1,INF)
                Dn.add_edge(H+1+j,H+W+1,INF)
                t=(i,j)
    if s[0]==t[0] or s[1]==t[1]:
        print(-1)
    else:
        ans=Dn.max_flow(0,1+H+W)
        print(ans)

Solution (Python):
import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf

H, W = map(int, input().split())
G = [input() for _ in range(H)]
T = Dinic(H+W)
inf = 10**9+7
SS = []
for i in range(H):
    for j in range(W):
        if G[i][j] == '.':
            continue
        if G[i][j] == 'o':
            T.addedge(i, H+j, 1)
            T.addedge(H+j, i, 1)
            continue
        SS.append(i)
        SS.append(H + j)
        T.addedge(i, H+j, inf)
        T.addedge(H+j, i, inf)
ans = T.getmf(SS[0], SS[-1])
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Solution (Python):


INF = 10 ** 9

que = [0] * 1024

def bfs(g, flow, parent, s1, s2, t1, t2):

    qf = 0
    que[0] = s1
    que[1] = s2
    ql = 2

    while qf < ql:
        u = que[qf]
        qf += 1
        for v in g[u]:
            if 0 <= flow[u][v] and parent[v] == -1:
                parent[v] = u
                if v != t1 and v != t2:
                    que[ql] = v
                    ql += 1
                else:
                    return 1, v

    return 0, 0


def solve(h, w, g, s, t):

    n = h + w
    si, sj = s
    ti, tj = t

    if si == ti or sj == tj:
        return -1

    f = 0
    flow = [[0] * n for _ in range(n)]

    while True:
        parent = [-1] * n
        parent[si] = -2
        parent[sj] = -2

        m, te = bfs(g, flow, parent, si, sj, ti, tj)
        if m == 0:
            break
        f += 1
        v = te
        while v != si and v != sj:
            u = parent[v]
            flow[u][v] -= 1
            flow[v][u] += 1
            v = u

    return f


def main():
    h, w = input().split()
    h = int(h)
    w = int(w)
    g = [[] for _ in range(h + w)]
    s = None
    t = None
    for i in range(h):
        a = input()
        for j in range(w):
            ch = a[j]
            if ch == 'o':
                g[i].append(h + j)
                g[h + j].append(i)
            elif ch == 'S':
                s = (i, h + j)
            elif ch == 'T':
                t = (i, h + j)


    print(solve(h, w, g, s, t))


if __name__ == '__main__':
    main()