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):
def main():
    
    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        flow = 0
        while True:
            used = [False]*n
            used2 = [0]*n
            q = [(s, 10**6)]
            ans = [0]
            while q:
                v, f = q[-1]
                a = ans[0]
                if a == 0:
                    if v == t:
                        ans[0] = f
                        continue
                    gkv, gv = gkey[v], g[v]
                    l, used[v] = len(gkv), True
                    while True:
                        i = used2[v]
                        used2[v] += 1
                        if i < l:
                            to = gkv[i]
                            cap, to2 = gv[to], [to, -to-1][to < 0]
                            if (not used[to2]) and cap:
                                q.append((to2, min(f, cap)))
                                break
                        else:
                            q.pop()
                            ans[0] = 0
                            break
                else:
                    q.pop()
                    if q:
                        v = q[-1][0]
                        i = used2[v]-1
                        to = gkey[v][i]
                        g[v][to] -= a
                        g[[to, -to-1][to < 0]][-v-1] += a
            if not ans[0]:
                return flow
            flow += ans[0]

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
def main():
    
    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        flow = 0
        while True:
            used = [False]*n
            used2 = [0]*n
            q = [(s, 10**6)]
            ans = [0]
            while q:
                v, f = q[-1]
                a = ans[0]
                if a == 0:
                    if v == t:
                        ans[0] = f
                        continue
                    gkv, gv = gkey[v], g[v]
                    l, used[v] = len(gkv), True
                    while True:
                        i = used2[v]
                        used2[v] += 1
                        if i < l:
                            to = gkv[i]
                            cap, to2 = gv[to], [to, -to-1][to < 0]
                            if (not used[to2]) and cap:
                                q.append((to2, min(f, cap)))
                                break
                        else:
                            q.pop()
                            ans[0] = 0
                            break
                else:
                    q.pop()
                    if q:
                        v = q[-1][0]
                        i = used2[v]-1
                        to = gkey[v][i]
                        g[v][to] -= a
                        g[[to, -to-1][to < 0]][-v-1] += a
            if not ans[0]:
                return flow
            flow += ans[0]

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
def main():
    
    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        def dfs():
            while q:
                v, t, f = q[-1]
                if ans[0] == 0:
                    if v == t:
                        ans[0] = f
                        continue
                    used[v] += 1
                    while True:
                        i = used2[v]
                        used2[v] += 1
                        if i < len(gkey[v]):
                            to = gkey[v][i]
                            cap = g[v][to]
                            if to < 0:
                                to2 = -to-1
                            else:
                                to2 = to
                            if used[to2] or cap == 0:
                                continue
                            q.append((to2, t, min(f, cap)))
                            break
                        else:
                            q.pop()
                            ans[0] = 0
                            break
                else:
                    q.pop()
                    if q:
                        v, t, f = q[-1]
                        i = used2[v]-1
                        to = gkey[v][i]
                        if to < 0:
                            to2 = -to-1
                        else:
                            to2 = to
                        g[v][to] -= ans[0]
                        g[to2][-v-1] += ans[0]

        flow = 0
        while True:
            used = [0]*n
            used2 = [0]*n
            q = [(s, t, 10**6)]
            ans = [0]
            dfs()
            if not ans[0]:
                return flow
            flow += ans[0]

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(1000000)
    

    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        def dfs(v, t, f):
            q.append(v)
            if v == t:
                return f
            used[v] += 1
            for i in range(len(gkey[v])):
                to = gkey[v][i]
                cap = g[v][to]
                if to < 0:
                    to2 = -to-1
                else:
                    to2 = to
                if used[to2] or cap == 0:
                    continue
                d = dfs(to2, t, min(f, cap))
                if d > 0:
                    g[v][to] -= d
                    g[to2][-v-1] += d
                    return d
            q.pop()
            return 0

        flow = 0
        while True:
            used = [0]*n
            q = []
            f = dfs(s, t, 10**100)
            if not q:
                return flow
            flow += f

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(1000000)
    

    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        def dfs(v, t, f):
            q.append(v)
            if v == t:
                return f
            used[v] += 1
            for i in range(len(gkey[v])):
                to = gkey[v][i]
                cap = g[v][to]
                if to < 0:
                    to2 = -to-1
                else:
                    to2 = to
                if used[to2] or cap == 0:
                    continue
                d = dfs(to2, t, min(f, cap))
                if d > 0:
                    g[v][to] -= d
                    g[to2][-v-1] += d
                    return d
            q.pop()
            return 0

        flow = 0
        while True:
            used = [0]*n
            q = []
            f = dfs(s, t, 10**100)
            if not q:
                return flow
            flow += f

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v  
        self.ite = [0]*v  
    def add_edge(self, fr, to, cap):
        self.G[fr].append([to, cap, len(self.G[to])])
        self.G[to].append([fr, 0, len(self.G[fr])-1])
    def bfs(self, s):  
        self.level = [-1]*self.v  
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0: 
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[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.G[e[0]][e[2]][1] += 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.ite = [0]*self.v  
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)

H, W = MAP()
a = [list(input()) for _ in range(H)]
D = Dinic(H+W+2)

for i in range(H):
    for j in range(W):
        if a[i][j] == "S":
            sy, sx = i, j
            D.add_edge(0, i+1, INF)
            D.add_edge(0, H+j+1, INF)
        elif a[i][j] == "T":
            gy, gx = i, j
            D.add_edge(i+1, H+W+1, INF)
            D.add_edge(H+j+1, H+W+1, INF)
        elif a[i][j] == "o":
            D.add_edge(i+1, H+j+1, 1)
            D.add_edge(H+j+1, i+1, 1)

if sy == gy or sx == gx:
	print(-1)
	exit()

print(D.max_flow(0, H+W+1))

Solution (Python):
def dfs(v,t,f,used,graph):
    if v==t:
        return f
    used[v] = True
    for to in graph[v]:
        c = graph[v][to]
        if used[to] or c==0:
            continue
        d = dfs(to,t,min(f,c),used,graph)
        if d>0:
            graph[v][to] -= d
            graph[to][v] += d
            return d
    return 0
 
def max_flow(s,t,graph):
    flow = 0
    while True:
        used = [False]*len(graph)
        f = dfs(s,t,float('inf'),used,graph)
        flow += f
        if f==0 or f==float('inf'):
            return flow
 
H,W = map(int,input().split())

a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]

graph = [{} for _ in range(H+W+2)]

for h in range(H):
    for w in range(W):
        if a[h][w]=='o':
            graph[h][H+w] = 1
            graph[H+w][h] = 1
        if a[h][w]=='S':
            graph[H+W][h] = float('inf')
            graph[H+W][H+w] = float('inf')
            graph[h][H+W] = 0
            graph[H+w][H+W] = 0
        if a[h][w]=='T':
            graph[H+W+1][h] = 0
            graph[H+W+1][H+w] = 0
            graph[h][H+W+1] = float('inf')
            graph[H+w][H+W+1] = float('inf')

ans = max_flow(H+W,H+W+1,graph)
if ans == float('inf'):
    ans = -1

print(ans)

Solution (Python):
H,W = map(int,input().split())
A = [input() for i in range(H)]
sy = sx = ty = tx = -1
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='S':
            sy,sx = i,j
        if c=='T':
            ty,tx = i,j
if sy==ty or sx==tx:
    print(-1)
    exit()

S = H+W
G = S+1
P = G+1
es = [[] for i in range(P)] 

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,0,len(es[fr])-1])
INF = float('inf')
add_edge(S, sy, INF)
add_edge(S, H+sx, INF)
add_edge(ty, G, INF)
add_edge(H+tx, G, INF)
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c!='o': continue
        add_edge(i, H+j, 1)
        add_edge(H+j, i, 1)

level = [0] * P
iters = [0] * P
from collections import deque
def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * P
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d 
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * P
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(dinic_max_flow(S,G))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class Dinic():
    def __init__(self, G, source, sink):
        self.G = G
        self.sink = sink
        self.source = source

    def add_edge(self, u, v, cap):
        self.G[u][v] = cap
        self.G[v][u] = 0

    def bfs(self):
        level = defaultdict(int)
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for u in q:
                for v, cap in self.G[u].items():
                    if cap == 0:
                        continue
                    if level[v]:
                        continue
                    level[v] = d
                    qq += [v]
            q = qq
        self.level = level

    def dfs(self, u, f):
        if u == self.sink:
            return f
        for v, cap in self.iter[u]:
            if cap == 0 or self.level[v] != self.level[u] + 1:
                continue
            d = self.dfs(v, min(f, cap))
            if d:
                self.G[u][v] -= d
                self.G[v][u] += d
                return d
        return 0

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.iter = {u: iter(self.G[u].items()) for u in self.G}
            while True:
                f = self.dfs(self.source, INF)
                if f == 0:
                    break
                flow += f
        return flow

h, w = LI()
s = SR(h)
G = defaultdict(lambda:defaultdict(int))
for i in range(h):
    for j in range(w):
        if s[i][j] == 'o':
            G[i][h + j] = 1
            G[h + j][i] = 1
        elif s[i][j] == 'S':
            G[h + w][i] = INF
            G[h + w][h + j] = INF
        elif s[i][j] == 'T':
            G[i][h + w + 1] = INF
            G[h + j][h + w + 1] = INF

ans = Dinic(G, h + w, h + w + 1).max_flow()
print(ans if ans < INF else -1)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

    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 = [-1] * 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] == -1:
                    level[w] = lv
                    deq.append(w)
        return level[t] != -1

    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.it[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.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 ** 18
        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

h, w = LI()
dinic = Dinic(h + w + 2)
s = SR(h)
for i in range(h):
    for j in range(w):
        if s[i][j] == 'o':
            dinic.add_multi_edge(i, h + j, 1, 1)
        elif s[i][j] == 'S':
            dinic.add_edge(h + w, i, INF)
            dinic.add_edge(h + w, h + j, INF)
        elif s[i][j] == 'T':
            dinic.add_edge(i, h + w + 1, INF)
            dinic.add_edge(h + j, h + w + 1, INF)

ans = dinic.flow(h + w, h + w + 1)
print(ans if ans < INF else -1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = None
        self.it = None
    
    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.graph[fr].append(forward)
        self.graph[to].append(backward)
    
    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.graph[v1].append(edge1)
        self.graph[v2].append(edge2)
    
    def bfs(self, s, t):
        self.level = level = [-1] * self.n
        deq = deque([s])
        level[s] = 0
        G = self.graph
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] == -1:
                    level[w] = lv
                    deq.append(w)
        return level[t] != -1
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.it[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.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 ** 18
        while self.bfs(s, t):
            *self.it, = map(iter, self.graph)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def solve():
    H, W = map(int, rl().split())
    INF = 10 ** 18
    s = H + W
    t = s + 1
    dinic = Dinic(t + 1)
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == 'o':
                dinic.add_multi_edge(i, H + j, 1, 1)
            elif line[j] == 'S':
                dinic.add_edge(s, i, INF)
                dinic.add_edge(s, H + j, INF)
            elif line[j] == 'T':
                dinic.add_edge(i, t, INF)
                dinic.add_edge(H + j, t, INF)
    
    ans = dinic.flow(s, t)
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    solve()

Solution (Python):

from collections import deque
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i 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_bidirectional_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**30
		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

H, W = map(int, input().split())
a = [input() for _ in range(H)]
d = Dinic(H+W+2)
for i in range(H):
	for j in range(W):
		if a[i][j] == "S":
			d.add_edge(H+W, i, 10**5)
			d.add_edge(H+W, H+j, 10**5)
		elif a[i][j] == "T":
			d.add_edge(i, H+W+1, 10**5)
			d.add_edge(H+j, H+W+1, 10**5)
		elif a[i][j] == "o":
			d.add_edge(i, H+j, 1)
			d.add_edge(H+j, i, 1)
ans = d.flow(H+W, H+W+1)
if ans > 10000:
	print(-1)
else:
	print(ans)

Solution (Python):

"""
この問題は最小カットに帰着できる。但し、h*wの頂点を持つと間に合わないので、H軸とW軸を独立に考える。
縦H個、横W個の頂点を持つ。
ある座標h,wがoの時、頂点H[h]とW[w]と容量1のネットワークでつなぐ。[sourse,h0,h1,...hH,w0,w1,...wW,sink]
startとgoalを最大流の始点、終点として持つのではなく、それとは別にsourse,sinkの2頂点を作る。
startとsourse,goalとsinkを容量INFでつなぐことにより、より簡単に最小カットを求めることが可能になる。
よって、グラフ長はH*W+2となる。
ネットワーク自体は無向なので、undirectedを使用する。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0


"""
class Dinicの使い方:
initは、Dinic(頂点数,始点,終点)で行う。
最大流の典型として、実際に問題に与えられる始点、終点とは別に、その始点sと終点tを、
新たに作成したsource(S)とsink(T)にcap=INFでつなげることで、実質始点と終点をそのままで使用することができる。
このテクニックにより簡単になる問題が多いので、いっそそれを前提にしちゃえというのがこのテンプレ。
与えられるグラフの頂点数をNとして、N+2(sourceとsinkの+2)で初期化し、source=0,sink=N+1とすると良い。
辺を張る際に、
有向グラフの場合は、add_edge(from,to,capacity)
無向グラフの場合は、add_edge_undirected(from,to,capacity)　とする。
最後にmax_flowで最大流を求めるが、INFが10**18と非常に大きいのは、sourceからsinkへのパスが存在しなかった場合、
INF以上の値が帰ってくる為である。
「もしそのような最大流が存在しないなら-1を出力」というような条件で、
f = max_flow()
if f == INF:
    print(-1)
とやると、fがINFより大きい場合があるので、
if f >= INF:
    print(-1)
else:
    print(f)
とする必要がある。 
"""
from collections import deque
class Dinic():
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
 
    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) 
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1]) 
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

source = 0
sink = H+W+1
network = Dinic(H+W+2,source,sink)
INF = 10**18

for i in range(1,H+1):
    for j,ox in enumerate(maze[i-1],1):
        if ox == "x":
            continue
        elif ox == "o":
            network.add_edge_undirected(i,H+j,1)
        elif ox == "S":
            network.add_edge_undirected(source,i,INF)
            network.add_edge_undirected(source,H+j,INF)
        elif ox == "T":
            network.add_edge_undirected(i,sink,INF)
            network.add_edge_undirected(H+j,sink,INF)

f = network.max_flow()
if f >= INF:
    print(-1)
else:
    print(f)