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: Runtime Error

Solution code:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        if v==t:
            return f
        self.used[v]=True
        for i in range(len(self.adj[v])):
            (nex_id,nex_cap,nex_rev) = self.adj[v][i]
            if not self.used[nex_id] and nex_cap>0:
                d = self.dfs(nex_id,t,min(f,nex_cap))
                if d>0:
                    #decrease capacity to denote use it with d flow
                    self.adj[v][i][1]-=d
                    self.adj[nex_id][nex_rev][1]+=d
                    return d
        return 0

    def max_flow(self,s:int,t:int):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*self.V
            f = self.dfs(s,t,float("inf"))
            if f==0:
                return flow
            else:
                flow+=f


H,W = map(int,input().split())
grid=[[v for v in input()] for _ in range(H)]

F = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        if grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        if grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Submission status: Runtime Error

Solution code:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        if v==t:
            return f
        self.used[v]=True
        for i in range(len(self.adj[v])):
            (nex_id,nex_cap,nex_rev) = self.adj[v][i]
            if not self.used[nex_id] and nex_cap>0:
                d = self.dfs(nex_id,t,min(f,nex_cap))
                if d>0:
                    #decrease capacity to denote use it with d flow
                    self.adj[v][i][1]-=d
                    self.adj[nex_id][nex_rev][1]+=d
                    return d
        return 0

    def max_flow(self,s:int,t:int):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*self.V
            f = self.dfs(s,t,float("inf"))
            if f==0:
                return flow
            else:
                flow+=f


H,W = map(int,input().split())
grid=[[v for v in input()] for _ in range(H)]

F = FordFulkerson(H*W*2*10)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Submission status: Runtime Error

Solution code:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        if v==t:
            return f
        self.used[v]=True
        for i in range(len(self.adj[v])):
            (nex_id,nex_cap,nex_rev) = self.adj[v][i]
            if not self.used[nex_id] and nex_cap>0:
                d = self.dfs(nex_id,t,min(f,nex_cap))
                if d>0:
                    #decrease capacity to denote use it with d flow
                    self.adj[v][i][1]-=d
                    self.adj[nex_id][nex_rev][1]+=d
                    return d
        return 0

    def max_flow(self,s:int,t:int):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*self.V
            f = self.dfs(s,t,float("inf"))
            if f==0:
                return flow
            else:
                flow+=f


H,W = map(int,input().split())
grid=[[v for v in input()] for _ in range(H)]

F = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,float("inf"))
                F.add_edge(i*W+k+H*W,i*W+j,float("inf"))

for i in range(W):
    for j in range(H):
        for k in range(j+1,H):
            if grid[j][i]=="o" and grid[k][i]=="o":
                F.add_edge(j*W+i+H*W,k*W+i,float("inf"))
                F.add_edge(k*W+i+H*W,j*W+i,float("inf"))




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Submission status: Runtime Error

Solution code:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        if v==t:
            return f
        self.used[v]=True
        for i in range(len(self.adj[v])):
            (nex_id,nex_cap,nex_rev) = self.adj[v][i]
            if not self.used[nex_id] and nex_cap>0:
                d = self.dfs(nex_id,t,min(f,nex_cap))
                if d>0:
                    #decrease capacity to denote use it with d flow
                    self.adj[v][i][1]-=d
                    self.adj[nex_id][nex_rev][1]+=d
                    return d
        return 0

    def max_flow(self,s:int,t:int):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*self.V
            f = self.dfs(s,t,float("inf"))
            if f==0:
                return flow
            else:
                flow+=f


H,W = map(int,input().split())
grid=[[v for v in input()] for _ in range(H)]

F = FordFulkerson(H*W*2)
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            sy,sx = i,j
            grid[i][j]="o"
        elif grid[i][j]=="T":
            gy,gx=i,j
            grid[i][j]="o"
        elif grid[i][j]=="o":
            #in node and out node
            F.add_edge(i*W+j,i*W+j+H*W,1)

for i in range(H):
    for j in range(W):
        for k in range(j+1,W):
            if grid[i][j]=="o" and grid[i][k]=="o":
                #out->in
                F.add_edge(i*W+j+H*W,i*W+k,1)
                F.add_edge(i*W+k+H*W,i*W+j,1)

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




if sy==gy or sx==gx:
    print(-1)
    exit()
print(F.max_flow(sy*W+sx+H*W,gy*W+gx))

Submission status: Runtime Error

Solution code:
class FordFulkerson:
    """max-flow-min-cut
    O(F|E|)
    """

    def __init__(self,V:int):
        """
        Arguments:
            V:num of vertex
            adj:adjedscent list(adj[from]=(to,capacity,id))
        """
        self.V = V
        self.adj=[[] for _ in range(V)]
        self.used=[False]*V

    def add_edge(self,fro:int,to:int,cap:int):
        """
        Arguments:
            fro:from
            to: to
            cap: capacity of the edge
            f: max flow value
        """
        #edge
        self.adj[fro].append([to,cap,len(self.adj[to])])
        #rev edge
        self.adj[to].append([fro,0,len(self.adj[fro])-1])

    def dfs(self,v,t,f):
        """
        search increasing path
        """
        if v==t:
            return f
        self.used[v]=True
        for i in range(len(self.adj[v])):
            (nex_id,nex_cap,nex_rev) = self.adj[v][i]
            if not self.used[nex_id] and nex_cap>0:
                d = self.dfs(nex_id,t,min(f,nex_cap))
                if d>0:
                    #decrease capacity to denote use it with d flow
                    self.adj[v][i][1]-=d
                    self.adj[nex_id][nex_rev][1]+=d
                    return d
        return 0

    def max_flow(self,s:int,t:int):
        """calculate maxflow from s to t
        """
        flow=0
        self.used = [False]*self.V
        #while no increasing path is found
        while True:
            self.used = [False]*self.V
            f = self.dfs(s,t,float("inf"))
            if f==0:
                return flow
            else:
                flow+=f


H,W = map(int,input().split())
grid=[[v for v in input()] for _ in range(H)]

F = FordFulkerson(H*W)
for i in range(H):
    for j in range(W):
        if grid[i][j]!="o":
            continue
        for k in range(j+1,W):
            if grid[i][k]=="o":
                F.add_edge(i*W+j,i*W+k,1)
                F.add_edge(i*W+k,i*W+j,1)
for i in range(W):
    for j in range(H):
        if grid[j][i]!="o":
            continue
        for k in range(j+1,H):
            if grid[k][i]=="o":
                F.add_edge(j*W+i,k*W+i,1)
                F.add_edge(k*W+i,j*W+i,1)

s=-1
g=-1
for i in range(H):
    for j in range(W):
        if grid[i][j]=="S":
            s=i*W+j
        if grid[i][j]=="T":
            g=i*W+j

s_i = s//W
s_j = s%W
g_i = g//W
g_j = g%W

if s_i==g_i or s_j == g_j:
    print(-1)
    exit()

for i in range(H):
    for j in range(W):
        if i==s_i or j==s_j and grid[i][j]=="o":
            F.add_edge(s,i*W+j,1)
        if i==g_i or j==g_j and grid[i][j]=="o":
            F.add_edge(i*W+j,g,1)
        pass

print(F.max_flow(s,g))

Submission status: Runtime Error

Solution code:
# AOJ GRL_6_A "Maximum Flow"
# Ford-Fulkerson method

import sys
input = sys.stdin.readline

INF = 10**18

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


def make():
    state = [list(input().rstrip()) for _ in range(H)]
    graph = [{} for _ in range(2*V)]

    start = -1
    finish = -1

    for h in range(H):
        Node = []
        for w in range(W):
            if state[h][w] != ".":
                Node.append(h*W+w)
            if state[h][w] == "S":
                start = h*W + w
            if state[h][w] == "T":
                finish = h*W + w
        L = len(Node)
        for i in range(L):
            v = Node[i]
            for j in range(i+1, L):
                u = Node[j]
                graph[u][v] = 1
                graph[v][u] = 1


    for w in range(W):
        Node = []
        for h in range(H):
            if state[h][w] != ".":
                Node.append(h*W+w)
        L = len(Node)
        for i in range(L):
            v = Node[i]
            if v not in {start, finish}: v += V
            for j in range(i+1, L):
                u = Node[j]
                if u not in {start, finish}: u += V
                graph[u][v] = 1
                graph[v][u] = 1
    
    for i in range(V):
        if i != start and i != finish:
            u, v = i, i+V
            graph[u][v] = 1
            graph[v][u] = 1
    
    return graph, start, finish


def dfs2(start, finish, graph):
    Flow = [INF]*len(graph)
    used = [False]*len(graph)
    Par = [-1]*len(graph)
    stack = [start]
    used[start] = True
    while stack:
        v = stack.pop()
        if v == finish:
            d = Flow[v]
            while v != start:
                nv = Par[v]
                graph[nv][v] -= d
                graph[v][nv] += d
                if not graph[nv][v]:
                    del graph[nv][v]
                v = nv
            return d, graph
        for i, (nv, ncap) in enumerate(graph[v].items()):
            if not used[nv] and ncap > 0:
                used[nv] = True
                stack.append(nv)
                Par[nv] = v
                Flow[nv] = min(Flow[v], ncap)
    return 0, graph

# solve
def max_flow(start, finish, graph):
    flow = 0
    while True:
        f, graph = dfs2(start, finish, graph)
        if f == 0: return flow
        flow += f


def main():
    graph, start, finish = make()
    ans = max_flow(start, finish, graph)

    if start//W == finish//W or start%W == finish%W:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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())

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

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

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

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: Runtime Error

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

from collections import deque
class Dinic():
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
 
    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1]) # 逆辺を cap 0 で追加
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

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

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

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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(s)
            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)
A = [list(str(input())) for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == 'S':
            start = h*H + w
        elif A[h][w] == 'T':
            goal = h*H + w

for h in range(H):
    leaves = [i for i in range(W) if A[h][i] == 'o' or A[h][i] == 'S' or A[h][i] == 'T']
    if len(leaves) <= 1:
        continue
    else:
        for i, v in enumerate(leaves):
            for j in range(i+1, len(leaves)):
                graph.add(h*H+v, h*H+leaves[j], 1, False)

for w in range(W):
    leaves = [i for i in range(H) if A[i][w] == 'o' or A[i][w] == 'S' or A[i][w] == 'T']
    if len(leaves) <= 1:
        continue
    else:
        for i, v in enumerate(leaves):
            for j in range(i+1, len(leaves)):
                graph.add(v*H+w, leaves[j]*H+w, 1, False)


if start % W == goal % W or start // W == goal // W:
    print(-1)
    quit()

print(graph.maxFlow(start, goal))

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)

def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}

H, W = ILI()
board = [list(input()) for __ in range(W)]

leaf_h = [[] for __ in range(H)]
leaf_w = [[] for __ in range(W)]
S = tuple()
T = tuple()
b_break = True

for i, row in enumerate(board):
    for j, masu in enumerate(row):
        if masu == "o":
            leaf_h[i].append(j)
            leaf_w[j].append(i)
        elif masu == "S":
            S = (i, j)
        elif masu == "T":
            T = (i, j)

if S[0] == T[0] or S[1] == T[1]:
    print(-1)

ans = 0

l_first = []
for j in leaf_h[S[0]]:
    l_first.append((S[0], j))
for i in leaf_w[S[1]]:
    l_first.append((i, S[1]))

def jump(now, first):
    global leaf_h
    global leaf_w
    global ans
    global b_break
    
    if b_break:
        next = []
        for j in leaf_h[now[0]]:
            l_first.append((S[0], j))
        for i in leaf_w[now[1]]:
            l_first.append((i, S[1]))
        
        for n in next:
            if n[0] == T[0] or n[1] == T[1]:
                del leaf_h[first[0]][first[1]]
                del leaf_w[first[1]][first[0]]
                ans += 1
                b_break = False
                break
            else:
                jump(n, first)

for f in l_first:
    b_break = True
    jump(f, f)

print(ans)

Submission status: Runtime Error

Solution code:
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    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 add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow
h, w = map(int, raw_input().split())
A = [raw_input() for i in xrange(h)]
dinic = Dinic(2*h*w+2)
start = 2*h*w; end = 2*h*w+1
INF = 10**9+7
for i in xrange(h):
    for j in xrange(w):
        for k in xrange(h):
            dinic.add_edge(h*w + j + w*k, j + w*i, INF)
            dinic.add_edge(h*w + k + w*i, j + w*i, INF)
        c = A[i][j]
        if c is 'o':
            dinic.add_edge(j + w*i, h*w + j + w*i, 1)
        elif c is 'S':
            dinic.add_edge(start, h*w + j + w*i, INF)
        elif c is 'T':
            dinic.add_edge(j + w*i, end, INF)
ans = dinic.max_flow(start, end)
if ans == INF:
    print -1
else:
    print ans