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:
# Ford-Fulkerson algorithm
class FordFulkerson:
    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_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 dfs(self, v, t, f):
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.G[v]:
            w, cap, rev = e
            if cap and not used[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
        f = INF = 10**9 + 7
        N = self.N
        while f:
            self.used = [0]*N
            f = self.dfs(s, t, INF)
            flow += f
        return flow

H,W=map(int,input().split())
a=[]
for i in range(H):
    a.append(input())

leaf=[]
for i in range(H):
    for j in range(W):
        if a[i][j]=="o":
            leaf.append((i,j))
        elif a[i][j]=="S":
            s=(i,j)
        elif a[i][j]=="T":
            t=(i,j)

inf=300
L=FordFulkerson(H+W+2+2*len(leaf))
for i in range(len(leaf)):
    x,y=leaf[i]
    X,Y=x+1,y+H+1
    index=2*i+H+W+1
    L.add_edge(X,index,inf)
    L.add_edge(Y,index,inf)
    L.add_edge(index,index+1,1)
    L.add_edge(index+1,X,inf)
    L.add_edge(index+1,Y,inf)

i,j=s
L.add_edge(0,i+1,inf)
L.add_edge(0,j+H+1,inf)
i,j=t
L.add_edge(i+1,H+W+2+2*(len(leaf))-1,inf)
L.add_edge(j+H+1,H+W+2+2*(len(leaf))-1,inf)
ans=L.flow(0,H+W+2+2*(len(leaf))-1)
print(ans if inf>ans else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w = map(int, input().split())
    s = [input() for _ in [0]*h]
    g = [dict() for _ in [0]*(h+w+2)]

    for i in range(h):
        for j in range(w):
            if s[i][j] == "S":
                g[0][i+1] = [200, 0]
                g[0][h+j+1] = [200, 0]
            elif s[i][j] == "T":
                g[i+1][h+w+1] = [200, 0]
                g[h+j+1][h+w+1] = [200, 0]
            elif s[i][j] == "o":
                g[i+1][h+j+1] = [1, 0]
                g[h+j+1][i+1] = [1, 0]

    # 最大流問題を解く関数
    def max_flow(graph_temp, start, end):
        from copy import deepcopy
        graph = deepcopy(graph_temp)

        # DFSを行いpathを算出する部分
        def dfs(start, end, graph):
            path = [start]
            memo = [False]*len(graph)
            memo[start] = True
            while path:
                p = path[-1]
                for b, (c, flow) in graph[p].items():
                    if memo[b] is False and c-flow != 0:
                        memo[b] = True
                        path.append(b)
                        if path[-1] == end:
                            return path
                        break
                else:
                    path.pop(-1)

        # 求めたpathについて水を流す
        def flow_calc(graph, path):
            min_c = 10**20
            for i, p in enumerate(path[1:]):
                min_c = min(min_c, graph[path[i]][p][0]-graph[path[i]][p][1])
            for i, p in enumerate(path[1:]):
                graph[path[i]][p][1] += min_c

        # 残余グラフを作る
        def create_rest(graph):
            l = len(graph)
            rest = [dict() for _ in [0]*l]
            for i, element in list(enumerate(graph)):
                for b, (c, flow) in element.items():
                    if flow != 0:
                        rest[b][i] = [flow, 0]
                    if flow != c:
                        rest[i][b] = [c-flow, 0]
            return rest

        # 残余グラフを反映させる
        def rest_reflect(graph, rest):
            for i, z in enumerate(rest):
                for j, (i0, i1) in z.items():
                    if i1 > 0:
                        if j in graph[i].keys():
                            graph[i][j][1] += i1
                        else:
                            graph[j][i][1] -= i1

        # 計算を行う。一旦通常のグラフ上でDFSを行い、最後に残余グラフで調整する
        while True:
            path = dfs(start, end, graph)
            if path is None:
                break
            else:
                flow_calc(graph, path)
        while True:
            rest = create_rest(graph)
            path = dfs(start, end, rest)
            if path is None:
                break
            flow_calc(rest, path)
            rest_reflect(graph, rest)
        # return graph  # 実際の最大流グラフが知りたい場合はこちらをreturnする
        return sum([j for i, j in graph[0].values()])

    m = max_flow(g, 0, h+w+1)

    if m >= 200:
        print(-1)
    else:
        print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
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  # DFSでの探索が済んでいるか
    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):  # BFSで深さ決定,sがstart
        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: ###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  # DFSで増加パス探索,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  # cap減少
                    self.G[e[0]][e[2]][1] += d  # 逆辺のcap増加
                    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  # DFSでの探索が済んでいるか否か
            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(2*H*W)

for i in range(H):
	for j in range(W):
		if a[i][j] == "S":
			sy, sx = i, j
		elif a[i][j] == "T":
			gy, gx = i, j
			a[i][j] = "o"

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

for i in range(H):
	for j in range(W):
		if a[i][j] == "o":
			D.add_edge(W*i+j, H*W+W*i+j, 1)
			for k in range(H):
				if i == k:
					continue
				if a[k][j] == "o":
					D.add_edge(H*W+W*i+j, W*k+j, 1)
			for k in range(W):
				if j == k:
					continue
				if a[i][k] == "o":
					D.add_edge(H*W+W*i+j, W*i+k, 1)
		elif a[i][j] == "S":
			for k in range(H):
				if i == k:
					continue
				if a[k][j] == "o":
					D.add_edge(W*i+j, W*k+j, 1)
			for k in range(W):
				if j == k:
					continue
				if a[i][k] == "o":
					D.add_edge(W*i+j, W*i+k, 1)
print(D.max_flow(W*sy+sx, W*gy+gx))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
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:
            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)]

H,W=100,100
a = [['o']*W for i in range(H)]
a[0][0]='S'
a[-1][-1]='T'

def encode(h,w):
    return h*W+w

def decode(d):
    return (d//W,d%W)

ans = 10**9
for h in range(H):
    for w in range(W):
        if a[h][w]=='S':
            s = encode(h,w)
            a[h][w]='o'
        if a[h][w]=='T':
            t = encode(h,w)
            a[h][w]='o'

if decode(s)[0]==decode(t)[0] or decode(s)[1]==decode(t)[1]:
    ans = -1

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

for h in range(H):
    for w in range(W):
        if a[h][w]=='.':
            continue
        for i in range(H):
            if i==h:
                continue
            if a[i][w]=='.':
                continue
            graph[encode(h,w)][encode(i,w)] = 1
            graph[encode(i,w)][encode(h,w)] = 1
        for j in range(W):
            if j==w:
                continue
            if a[h][j]=='.':
                continue
            graph[encode(h,w)][encode(h,j)] = 1
            graph[encode(h,j)][encode(h,w)] = 1

ans = min(ans,max_flow(s,t,graph))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class Dinic:
    """ 最大流(Dinic) """

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        from collections import deque

        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
grid = build_grid(H, W, '', str, space=0)

# 最大流：頂点は各行全体、各列全体、始点、終点
dn = Dinic(H+W+2)
s = H + W
t = H + W + 1
for i in range(H):
    for j in range(W):
        if grid[i][j] == 'o':
            dn.add_link(i, H+j, 1)
            dn.add_link(H+j, i, 1)
        elif grid[i][j] == 'S':
            dn.add_link(s, i, INF)
            dn.add_link(s, H+j, INF)
        elif grid[i][j] == 'T':
            dn.add_link(i, t, INF)
            dn.add_link(H+j, t, INF)

ans = dn.max_flow(s, t)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

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_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

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = list(input())
		A.append(a)
	
	S = None
	T = None
	sx = None
	sy = None
	tx = None
	ty = None
	MM = H * W
	DD = Dinic(2 * MM)
	for i in range(H):
		for j in range(W):
			DD.add_edge(i * W + j, i * W + j + MM, 1)
			if A[i][j] == "S":
				S = i * W + j
				sx = j; sy = i
				A[i][j] = "o"
			if A[i][j] == "T":
				T = i * W + j
				tx = j; ty = i
				A[i][j] = "o"

	for i in range(H):
		for j in range(W):
			for k in range(j + 1, W):
				if A[i][j] == A[i][k] == "o":
					DD.add_edge(i * W + j + MM, i * W + k, 1)
					DD.add_edge(i * W + k + MM, i * W + j, 1)

	for i in range(H):
		for j in range(W):
			for k in range(i + 1, H):
				if A[i][j] == A[k][j] == "o":
					DD.add_edge(i * W + j + MM, k * W + j, 1)
					DD.add_edge(k * W + j + MM, i * W + j, 1)

	ans = DD.flow(S + MM, T)
	if sx == tx or sy == ty:
		ans = -1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

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_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

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = list(input())
		A.append(a)
	
	S = None
	T = None
	sx = None
	sy = None
	tx = None
	ty = None
	for i in range(H):
		for j in range(W):
			if A[i][j] == "S":
				S = i * W + j
				sx = j; sy = i
				A[i][j] = "o"
			if A[i][j] == "T":
				T = i * W + j
				tx = j; ty = i
				A[i][j] = "o"

	DD = Dinic(2 * H * W)

	for i in range(H):
		for j in range(W):
			for k in range(j + 1, W):
				if A[i][j] == A[i][k] == "o":
					DD.add_edge(i * W + j + H * W, i * W + k, 1)
					DD.add_edge(i * W + k + H * W, i * W + j, 1)

	for i in range(H):
		for j in range(W):
			for k in range(i + 1, H):
				if A[i][j] == A[k][j] == "o":
					DD.add_edge(i * W + j + H * W, k * W + j, 1)
					DD.add_edge(k * W + j + H * W, i * W + j, 1)

	#ノードの容量1で辺を張る
	for i in range(H):
		for j in range(W):
			DD.add_edge(i * W + j, i * W + j + H * W, 1)

	ans = DD.flow(S + H * W, T)
	if sx == tx or sy == ty:
		ans = -1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

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_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

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = list(input())
		A.append(a)
	
	S = None
	T = None
	sx = None
	sy = None
	tx = None
	ty = None
	for i in range(H):
		for j in range(W):
			if A[i][j] == "S":
				S = i * W + j
				sx = j; sy = i
				A[i][j] = "o"
			if A[i][j] == "T":
				T = i * W + j
				tx = j; ty = i
				A[i][j] = "o"

	DD = Dinic(2 * H * W)

	for i in range(H):
		for j in range(W):
			for k in range(j + 1, W):
				if A[i][j] == A[i][k] == "o":
					DD.add_edge(i * W + j + H * W, i * W + k, 1)
					DD.add_edge(i * W + k + H * W, i * W + j, 1)

	for i in range(H):
		for j in range(W):
			for k in range(i + 1, H):
				if A[i][j] == A[k][j] == "o":
					DD.add_edge(i * W + j + H * W, k * W + j, 1)
					DD.add_edge(k * W + j + H * W, i * W + j, 1)

	#ノードの容量1で辺を張る
	for i in range(H):
		for j in range(W):
			DD.add_edge(i * W + j, i * W + j + H * W, 1)

	ans = DD.flow(S + H * W, T)
	if sx == tx or sy == ty:
		ans = -1
	print(ans)

if __name__ == '__main__':
	main()

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 = ''
for _ in range(H):
    table += sys.stdin.readline().rstrip()

S = -1
T = -1
ok = True
size = H * W
graph = [[] for _ in range(H * W * 2)]
h = defaultdict(list)
w = defaultdict(list)
for n in range(len(table)):
    if table[n] == '.':
        continue
    i = n // W
    j = n % W
    if table[n] == 'S':
        S = n
        v = S
        u = S + size
        cap = IINF

        rev = [v, 0]
        edge = [u, cap, rev]
        rev.append(edge)
        graph[v].append(edge)
        graph[u].append(rev)

        ok &= T not in (h[i] + w[j])
    elif table[n] == 'T':
        T = n
        v = T
        u = T + size
        cap = IINF
        rev = [v, 0]
        edge = [u, cap, rev]
        rev.append(edge)
        graph[v].append(edge)
        graph[u].append(rev)

        ok &= S not in (h[i] + w[j])
    else:
        v = n
        u = n + size
        cap = 1
        rev = [v, 0]
        edge = [u, cap, rev]
        rev.append(edge)
        graph[v].append(edge)
        graph[u].append(rev)

    for m in h[i] + w[j]:
        v = n + size
        u = m
        cap = IINF
        rev = [v, 0]
        edge = [u, cap, rev]
        rev.append(edge)
        graph[v].append(edge)
        graph[u].append(rev)

        v = m + size
        u = n
        cap = IINF
        rev = [v, 0]
        edge = [u, cap, rev]
        rev.append(edge)
        graph[v].append(edge)
        graph[u].append(rev)
    h[i].append(n)
    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 ok:
    print(Dinic(residual=graph).maximum_flow(S, T))
else:
    print(-1)

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 = ''
for _ in range(H):
    table += sys.stdin.readline().rstrip()

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