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



Sample input:
3 3
S.o
.o.
o.T


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
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 = -1
T = -1
size = H * W
graph = [[] for _ in range(H * W * 2)]
h = defaultdict(list)
w = defaultdict(list)
for i, j in itertools.product(range(H), range(W)):
    if table[i][j] == '.':
        continue
    n = W * i + j
    if table[i][j] == 'S':
        S = n
        graph[S].append((S + size, IINF))
    elif table[i][j] == 'T':
        T = n
        graph[T].append((T + size, IINF))
    else:
        graph[n].append((n + size, 1))

    # ああ有向グラフにして流量制限したらいいのか
    for m in h[i]:
        graph[n + size].append((m, IINF))
        graph[m + size].append((n, IINF))
    h[i].append(n)

    for m in w[j]:
        graph[n + size].append((m, IINF))
        graph[m + size].append((n, IINF))
    w[j].append(n)


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


if (T, IINF) in graph[S + size]:
    print(-1)
else:
    print(Dinic(graph=graph).maximum_flow(S, T))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in v[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])-sum(c[s])

    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h*w)] for j in range(h*w)]
    v = [deque() for i in range(h*w)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                s = y*w+x
            if a[y][x] == "T":
                g = y*w+x
    if s%w == g%w or s//w == g//w:
        print(-1)
        quit()
    bfs_map = [1 for i in range(h*w)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    while q:
        p = q.pop()
        y = p//w
        x = p%w
        for i in range(h):
            if i != y and a[i][x] != ".":
                v[p].append(i*w+x)
                if p != g:
                    if i*w+x != s:
                        c[p][i*w+x] = 1
                    if bfs_map[i*w+x]:
                        bfs_map[i*w+x] = 0
                        q.append(i*w+x)
        for i in range(w):
            if i != x and a[y][i] != ".":
                v[p].append(y*w+i)
                if p != g:
                    if y*w+i != s:
                        c[p][y*w+i] = 1
                    if bfs_map[y*w+i]:
                        bfs_map[y*w+i] = 0
                        q.append(y*w+i)
    print(ford_fulkerson(s,g,c,h*w))
#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in v[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])-sum(c[s])

    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h*w)] for j in range(h*w)]
    v = [deque() for i in range(h*w)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                s = y*w+x
            if a[y][x] == "T":
                g = y*w+x
            if a[y][x] != ".":
                for i in range(h):
                    if y != i and a[i][x] != ".":
                        v[y*w+x].append(i*w+x)
                        if a[y][x] != "T" and a[i][x] != "S":
                            c[y*w+x][i*w+x] = 1
                for i in range(w):
                    if x != i and a[y][i] != ".":
                        v[y*w+x].append(y*w+i)
                        if a[y][x] != "T" and a[y][i] != "S":
                            c[y*w+x][y*w+i] = 1

    if s%w == g%w or s//w == g//w:
        print(-1)
        quit()
    o = 0
    print(ford_fulkerson(s,g,c,h*w))

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in v[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])-sum(c[s])

    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h*w)] for j in range(h*w)]
    v = [deque() for i in range(h*w)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                s = y*w+x
            if a[y][x] == "T":
                g = y*w+x
            if a[y][x] != "." and a[y][x] != "T":
                for i in range(h):
                    if y != i and a[i][x] != "." and a[i][x] != "S":
                        c[y*w+x][i*w+x] = 1
                        v[y*w+x].append(i*w+x)
                        v[i*w+x].append(y*w+x)
                for i in range(w):
                    if x != i and a[y][i] != "." and a[y][i] != "S":
                        c[y*w+x][y*w+i] = 1
                        v[y*w+x].append(y*w+i)
                        v[y*w+i].append(y*w+x)

    if s%w == g%w or s//w == g//w:
        print(-1)
        quit()
    o = 0
    print(ford_fulkerson(s,g,c,h*w))

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in v[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])-sum(c[s])

    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h*w)] for j in range(h*w)]
    v = [[] for i in range(h*w)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                s = y*w+x
            if a[y][x] == "T":
                g = y*w+x
            if a[y][x] != "." and a[y][x] != "T":
                for i in range(h):
                    if y != i and a[i][x] != "." and a[i][x] != "S":
                        c[y*w+x][i*w+x] = 1
                        v[y*w+x].append(i*w+x)
                        v[i*w+x].append(y*w+x)
                for i in range(w):
                    if x != i and a[y][i] != "." and a[y][i] != "S":
                        c[y*w+x][y*w+i] = 1
                        v[y*w+x].append(y*w+i)
                        v[y*w+i].append(y*w+x)

    if s%w == g%w or s//w == g//w:
        print(-1)
        quit()
    o = 0
    print(ford_fulkerson(s,g,c,h*w))

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    def bfs(s,g,n):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in range(n):
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in range(n+1):
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n):
        while 1:
            p,m = bfs(s,g,n)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])-sum(c[s])

    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h*w)] for j in range(h*w)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                s = y*w+x
            if a[y][x] == "T":
                g = y*w+x
            if a[y][x] != "." and a[y][x] != "T":
                for i in range(h):
                    if y != i and a[i][x] != "." and a[i][x] != "S":
                        c[y*w+x][i*w+x] = 1
                for i in range(w):
                    if x != i and a[y][i] != "." and a[y][i] != "S":
                        c[y*w+x][y*w+i] = 1

    if s%w == g%w or s//w == g//w:
        print(-1)
        quit()
    o = 0
    print(ford_fulkerson(s,g,c,h*w))
    
#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class Dinic:
    class Edge:
        def __init__(self, v, cap, rev):
            self.v = v
            self.cap = cap
            self.rev = rev

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

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

    # calculate the shortest distance from s
    def bfs(self, s):
        from collections import deque

        self.level = [-1] * self.V
        self.level[s] = 0
        queue = deque()
        queue.append(s)
        while queue:
            u = queue.popleft()
            for e in self.G[u]:
                if e.cap > 0 and self.level[e.v] == -1:
                    self.level[e.v] = self.level[u] + 1
                    queue.append(e.v)

    # find a path
    def dfs(self, u, t, f):
        if u == t:
            return f
        i = self.iter[u]
        while i < len(self.G[u]):
            e = self.G[u][i]
            if e.cap > 0 and self.level[u] < self.level[e.v]:
                d = self.dfs(e.v, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.G[e.v][e.rev].cap += d
                    return d
            i += 1
            self.iter[u] += 1
        return 0

    # find the max flow from s to v
    def max_flow(self, s, t):
        flow = 0
        INF = 10**18
        while True:
            self.bfs(s)
            if self.level[t] == -1:
                return flow
            self.iter = [0] * self.V
            while True:
                f = self.dfs(s, t, INF)
                if f == 0:
                    break
                flow += f

H, W = map(int, input().split())
a = [input().rstrip() for _ in range(H)]
flow = Dinic(2*H*W)
s = t = 0
INF = 10**9
for i in range(H):
    for j in range(W):
        if a[i][j] == '.':
            continue
        v = i * W + j
        flow.add_edge(v, H * W + v, 1)
        if a[i][j] == 'S':
            s = H * W + v
            for k in range(H):
                if a[k][j] == 'o':
                    flow.add_edge(s, k * W + j, INF)
                if a[k][j] == 'T':
                    print(-1)
                    exit()
            for k in range(W):
                if a[i][k] == 'o':
                    flow.add_edge(s, i * W + k, INF)
                if a[i][k] == 'T':
                    print(-1)
                    exit()
        if a[i][j] == 'T':
            t = v
        if a[i][j] == 'o':
            for k in range(H):
                if a[k][j] in 'oT':
                    flow.add_edge(H * W + v, k * W + j, INF)
            for k in range(W):
                if a[i][k] in 'oT':
                    flow.add_edge(H * W + v, i * W + k, INF)
print(flow.max_flow(s, t))

Submission status: Accepted

Solution code:
from collections import deque
class mf_graph:
    n=1
    g=[[] for i in range(1)]
    pos=[]
    def __init__(self,N):
        self.n=N
        self.g=[[] for i in range(N)]
    def add_edge(self,From,To,cap):
        assert 0<=From and From<self.n
        assert 0<=To and To<self.n
        assert 0<=cap
        m=len(self.pos)
        self.pos.append((From,len(self.g[From])))
        self.g[From].append({"to":To,"rev":len(self.g[To]),"cap":cap})
        self.g[To].append({"to":From,"rev":len(self.g[From])-1,"cap":0})
        return m
    def get_edge(self,i):
        m=len(self.pos)
        assert 0<=i and i<m
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        return {"from":self.pos[i][0],
                "to":_e["to"],
                "cap":_e["cap"]+_re["cap"],
                "flow":_re["cap"]}
    def edges(self):
        m=len(self.pos)
        result=[]
        for i in range(m):
            result.append(self.get_edge(i))
        return result
    def change_edge(self,i,new_cap,new_flow):
        m=len(self.pos)
        assert 0<=i and i<m
        assert 0<=new_flow and new_flow<=new_cap
        _e=self.g[self.pos[i][0]][self.pos[i][1]]
        _re=self.g[_e["to"]][_e["rev"]]
        _e["cap"]=new_cap-new_flow
        _re["cap"]=new_flow
    def flow(self,s,t,flow_limit=(2**31)-1):
        assert 0<=s and s<self.n
        assert 0<=t and t<self.n
        level=[0 for i in range(self.n)]
        Iter=[0 for i in range(self.n)]
        que=deque([])
        def bfs():
            for i in range(self.n):
                level[i]=-1
            level[s]=0
            que=deque([])
            que.append(s)
            while(len(que)>0):
                v=que.popleft()
                for e in self.g[v]:
                    if e["cap"]==0 or level[e["to"]]>=0:continue
                    level[e["to"]]=level[v]+1
                    if e["to"]==t:return
                    que.append(e["to"])
        def dfs(func,v,up):
            if (v==s):return up
            res=0
            level_v=level[v]
            for i in range(Iter[v],len(self.g[v])):
                e=self.g[v][i]
                if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue
                d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"]))
                if d<=0:continue
                self.g[v][i]["cap"]+=d
                self.g[e["to"]][e["rev"]]["cap"]-=d
                res+=d
                if res==up:break
            return res
        flow=0
        while(flow<flow_limit):
            bfs()
            if level[t]==-1:
                break
            for i in range(self.n):
                Iter[i]=0
            while(flow<flow_limit):
                f=dfs(dfs,t,flow_limit-flow)
                if not(f):break
                flow+=f
        return flow
    def min_cut(self,s):
        visited=[False for i in range(self.n)]
        que=deque([])
        que.append(s)
        while(len(que)>0):
            p=que.popleft()
            visited[p]=True
            for e in self.g[p]:
                if e["cap"] and not(visited[e["to"]]):
                    visited[e["to"]]=True
                    que.append(e["to"])
        return visited

H,W=map(int,input().split())
a=[list(input()) for i in range(H)]
G=mf_graph(H+W+2)
INF=10**9
s=H+W
t=H+W+1
for i in range(H):
    for j in range(W):
        if a[i][j]=="S":
            G.add_edge(s,i,INF)
            G.add_edge(s,j+H,INF)
        if a[i][j]=="T":
            G.add_edge(i,t,INF)
            G.add_edge(j+H,t,INF)
        if a[i][j]!=".":
            G.add_edge(i,j+H,1)
            G.add_edge(j+H,i,1)
ans=G.flow(s,t)
if ans>=INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque


class MF_graph(object):
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]  # to, rev, cap
        self.pos = []

    def add_edge(self, frm, to, cap):
        m = len(self.pos)
        self.pos.append((frm, len(self.g[frm])))
        self.g[frm].append([to, len(self.g[to]), cap])
        self.g[to].append([frm, len(self.g[frm]) - 1, 0])
        return m

    def get_edge(self, i):
        e_to, e_rev, e_cap = self.g[self.pos[i][0]][self.pos[i][1]]
        re_to, _, re_cap = self.g[e_to][e_rev]
        # from, to, cap, flow
        return (re_to, e_to, e_cap + re_cap, re_cap)

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, i, new_cap, new_flow):
        f, s = self.pos[i]
        rf, rs, _ = self.g[f][s]
        self.g[f][s][2] = new_cap - new_flow
        self.g[rf][rs][2] = new_flow
        return

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        level_v = self.level[v]
        for i in range(self.iter[v], len(self.g[v])):
            u_to, u_rev, _ = self.g[v][i]
            if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0:
                continue
            d = self.dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2]))
            if d <= 0:
                continue
            self.g[v][i][2] += d
            self.g[u_to][u_rev][2] -= d
            res += d
            if res == up:
                break
        return res

    def flow(self, s, t, flow_limit=10**18):
        self.iter = [0] * self.n

        flow = 0
        while flow < flow_limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            que = deque([s])
            while que:
                v = que.popleft()
                for u_to, _, u_cap in self.g[v]:
                    if u_cap == 0 or self.level[u_to] >= 0:
                        continue
                    self.level[u_to] = self.level[v] + 1
                    if u_to == t:
                        break
                    que.append(u_to)

            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < flow_limit:
                f = self.dfs(s, t, flow_limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [False] * self.n
        que = deque([s])
        while que:
            v = que.popleft()
            visited[v] = True
            for u_to, _, u_cap in self.g[v]:
                if u_cap and (not visited[u_to]):
                    visited[u_to] = True
                    que.append(u_to)
        return visited


H, W = map(int, input().split())
S = [input() for _ in range(H)]
inf = 10**18

g = MF_graph(H + W + 2)
source = H + W
sink = H + W + 1

for i in range(H):
    for j in range(W):
        if S[i][j] == "S":
            g.add_edge(source, i, inf)
            g.add_edge(source, H + j, inf)
        elif S[i][j] == "T":
            g.add_edge(i, sink, inf)
            g.add_edge(H + j, sink, inf)
        elif S[i][j] == "o":
            g.add_edge(i, H + j, 1)
            g.add_edge(H + j, i, 1)

flow = g.flow(source, sink)
if flow >= inf:
    print(-1)
else:
    print(flow)