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: Accepted

Solution code:
from collections import deque
INF = 10**9

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

    def add_edge(self, fr, to, cap):
        # edge consists of [dest, cap, id of reverse edge]
        forward = [to, cap, None]
        backward = [fr, 0, forward]
        forward[2] = backward
        self.edge[fr].append(forward)
        self.edge[to].append(backward)

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

    # takes start node and terminal node
    # create new self.level, return you can flow more or not 
    def bfs(self, s, t):
        self.level = [None] * self.n
        dq = deque([s])
        self.level[s] = 0
        while dq:
            v = dq.popleft()
            lv = self.level[v] + 1
            for dest, cap, _ in self.edge[v]: 
                if cap > 0 and self.level[dest] is None:
                    self.level[dest] = lv
                    dq.append(dest)
        return self.level[t] is not None

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

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

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

Submission status: Accepted

Solution code:
import collections
import queue


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

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

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

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

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


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

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

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

Submission status: Accepted

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 = H + W
T = H + W + 1
graph = [[] for _ in range(H + W + 2)]
for h, w in itertools.product(range(H), range(W)):
    if table[h][w] == '.':
        continue
    if table[h][w] == 'S':
        graph[S].append((h, IINF))
        graph[S].append((H + w, IINF))
    elif table[h][w] == 'T':
        graph[h].append((T, IINF))
        graph[H + w].append((T, IINF))
    graph[h].append((H + w, 1))
    graph[H + w].append((h, 1))


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

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

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

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

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

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

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

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import queue

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

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

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺
        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0;
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

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

        return 0

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

INF = 10 ** 9

que = [0] * 1024

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

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

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

    return 0, 0


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

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

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

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

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

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

    return f


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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])
    h,w = LI()
    a = SR(h)
    c = [[0 for i in range(h+w+2)] for j in range(h+w+2)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                c[0][y+1] = float("inf")
                c[0][h+x+1] = float("inf")
            if a[y][x] == "T":
                c[y+1][h+w+1] = float("inf")
                c[h+x+1][h+w+1] = float("inf")
            if a[y][x] == "o":
                c[y+1][h+x+1] = 1
                c[h+x+1][y+1] = 1
    ans = ford_fulkerson(0,h+w+1,c,h+w+2)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque

class Dinic:
    def __init__(self,n,edges):
        self.n=n
        self.edges=[[] for _ in range(n)]
        self.iter=[0]*n
        self.level=None
        self.graph(edges)
    def graph(self,E):
        edges=self.edges
        for fr,to,cap in E:
            edges[fr].append([to,cap,len(edges[to])])
            edges[to].append([fr,0,len(edges[fr])-1])
    def maxflow(self,source,sink):
        max_flow=0
        while True:
            self.bfs(source)
            if self.level[sink]<0:
                return max_flow
            self.iter=[0]*self.n
            flow=self.dfs(source,sink,float('inf'))
            while flow:
                max_flow+=flow
                flow=self.dfs(source,sink,float('inf'))
    def bfs(self,source):
        edges=self.edges
        level=[-1]*self.n
        level[source]=0
        q=deque([source])
        while q:
            fr=q.popleft()
            for to,cap,_ in edges[fr]:
                if cap>0>level[to]:
                    level[to]=level[fr]+1
                    q.append(to)
        self.level=level
    def dfs(self,source,sink,flow):
        if source==sink:
            return flow
        while self.iter[source]<len(self.edges[source]):
            to,cap,rev=self.edges[source][self.iter[source]]
            if cap>0 and self.level[source]<self.level[to]:
                f=self.dfs(to,sink,min(flow,cap))
                if f:
                    self.edges[source][self.iter[source]][1]-=f
                    self.edges[to][rev][1]+=f
                    return f
            self.iter[source]+=1
        return 0

inf=float('inf')
h,w=map(int,input().split())
Edges=[]
for x in range(h):
    s=list(input())
    for y in range(w):
        if s[y]=='S':
            Edges.append((0,x+1,inf))
            Edges.append((0,y+1+h,inf))
        elif s[y]=='T':
            Edges.append((x+1,h+w+1,inf))
            Edges.append((y+1+h,h+w+1,inf))
        elif s[y]=='o':
            Edges.append((x+1,y+1+h,1))
            Edges.append((y+1+h,x+1,1))
dinic=Dinic(h+w+2,Edges)
mf=dinic.maxflow(0,h+w+1)
print(-1 if mf==inf else mf)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
class FK:
    def __init__(self,n):
        self.table=[[0]*n for i in range(n)]
        self.n=n
    
    def add(self,x,y,f):
        self.table[x][y]=f
        
    def ford(self,s,t,f):
        self.visit[s]=True
        if s==t:
            return f
        for i in range(self.n):
            if (not self.visit[i]) and self.table[s][i]>0:
                df=self.ford(i,t,min(f,self.table[s][i]))
                if df>0:
                    self.table[s][i]-=df
                    self.table[i][s]+=df
                    return df
        return 0
    
    def flow(self,s,t):
        ans=0
        inf=10**20
        while True:
            self.visit=[False]*(self.n)
            df=self.ford(s,t,inf)
            if df==0:
                break
            ans+=df
        return ans

H,W=map(int,input().split())
C=[input() for i in range(H)]
maxflow=FK(W+H+2)
inf=10**20
for i in range(W):
    for j in range(H):
        if C[j][i]=='S':
            sx=i
            sy=j
            maxflow.add(0,i+1,inf)
            maxflow.add(0,W+1+j,inf)
            continue
        if C[j][i]=='T':
            gx=i
            gy=j
            maxflow.add(i+1,W+H+1,inf)
            maxflow.add(W+1+j,W+H+1,inf)
            continue
        if C[j][i]=='o':
            maxflow.add(i+1,W+1+j,1)
            maxflow.add(W+1+j,i+1,1)
#print(maxflow.table)
if gx==sx or gy==sy:
    print('-1')
    sys.exit()
ans=maxflow.flow(0,H+W+1)
print(ans)

Submission status: Accepted

Solution code:
# maximum flow
from collections import defaultdict

def ford_fulkerson(graph, start, end):
    """ 
    graph: [dict<int,int>]
    start: int
    end: int
    """
    INF = 10**9
    network = [defaultdict(int, paths) for paths in graph]

    def dfs(start, end, visited):
        """
        None: unreachable
        (): reached
        """
        if start == end:
            return ()
        visited.add(start)
        for next_, capacity in filter(lambda next_capacity: next_capacity[0] not in visited and next_capacity[1] > 0, network[start].items()):
            path = dfs(next_, end, visited)
            if path is not None:
                return (next_, capacity, path)
        return None

    def margin(path, min_margin=INF):
        if path == ():
            return min_margin
        _, capacity, remaining_path = path
        return margin(remaining_path, min(min_margin, capacity))

    def flush(start, path, amount):
        if path == ():
            return
        next_, _, remaining_path = path
        network[start][next_] -= amount
        network[next_][start] += amount
        flush(next_, remaining_path, amount)

    while True:
        path = dfs(start, end, set())
        if path == None:
            break
        flush(start, path, margin(path))

    return sum(cap for _, cap in graph[start].items()) - sum(cap for _, cap in network[start].items())

h, w = map(int, input().split())
A = [input() for _ in range(h)]

for i in range(h):
    for j in range(w):
        if A[i][j] == 'S':
            s = (i, j)
        if A[i][j] == 'T':
            t = (i, j)

if t[0] == s[0] or t[1] == s[1]:
    print(-1)
else:
    INF = 10**8
    si = h + w
    ti = h + w + 1
    graph = [{} for _ in range(h + w + 2)]
    graph[si][s[0]] = INF
    graph[si][h + s[1]] = INF
    graph[t[0]][ti] = INF
    graph[h + t[1]][ti] = INF
    for i in range(h):
        for j in range(w):
            if A[i][j] == 'o':
                graph[i][h + j] = 1
                graph[h + j][i] = 1
    print(ford_fulkerson(graph, si, ti))