Problem:


Score : 600 points

Problem Statement

There is a board with N rows and M columns.
The information of this board is represented by N strings S_1,S_2,\ldots,S_N.
Specifically, the state of the square at the i-th row from the top and the j-th column from the left is represented as follows:

S_{i,j}=. : the square is empty.

S_{i,j}=# : an obstacle is placed on the square.

S_{i,j}=o : a piece is placed on the square.

Yosupo repeats the following operation:

Choose a piece and move it to its right adjecent square or its down adjacent square.
Moving a piece to squares with another piece or an obstacle is prohibited.
Moving a piece out of the board is also prohibited.

Yosupo wants to perform the operation as many times as possible.
Find the maximum possible number of operations.

Constraints

1 \leq N \leq 50

1 \leq M \leq 50

S_i is a string of length M consisting of ., # and o.

1 \leq ( the number of pieces )\leq 100.
In other words, the number of pairs (i, j) that satisfy S_{i,j}=o is between 1 and 100, both inclusive.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the maximum possible number of operations in a line.

Sample Input 1

3 3
o..
...
o.#

Sample Output 1

4

Yosupo can perform operations 4 times as follows:

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#

Sample Input 2

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

Sample Output 2

24



Sample input:
3 3
o..
...
o.#


Sample output:
4

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappush, heappop

    class Mincostflow():
        def __init__(self, N):
            self.N = N
            self.adj = [[] for _ in range(N + 1)]
            self.inf = 1 << 60

        def add_edge(self, fr, to, cap, cost):
            # [to, cap, cost, rev]
            forward = [to, cap, cost, None]
            backward = forward[3] = [fr, 0, -cost, forward]
            self.adj[fr].append(forward)
            self.adj[to].append(backward)

        def flow(self, s, t, f):
            N = self.N
            adj = self.adj
            inf = self.inf

            res = 0
            H = [0] * (N + 1)
            prev_v = [0] * (N + 1)
            prev_e = [None] * (N + 1)

            dist0 = [inf] * (N + 1)
            dist = [inf] * (N + 1)

            while f:
                dist[:] = dist0
                dist[s] = 0
                pq = [(0, s)]
                while pq:
                    d, v = heappop(pq)
                    if d > dist[v]:
                        continue
                    r0 = dist[v] + H[v]
                    for e in adj[v]:
                        u, cap, cost, _ = e
                        if cap > 0 and r0 + cost - H[u] < dist[u]:
                            dist[u] = r = r0 + cost - H[u]
                            heappush(pq, (r, u))
                            prev_v[u] = v
                            prev_e[u] = e

                # flow f doesn't exist
                if dist[t] == inf:
                    return None

                for i in range(1, N + 1):
                    H[i] += dist[i]

                g = f
                v = t
                while v != s:
                    g = min(g, prev_e[v][1])
                    v = prev_v[v]
                f -= g
                res += g * H[t]
                v = t
                while v != s:
                    e = prev_e[v]
                    e[1] -= g
                    e[-1][1] += g
                    v = prev_v[v]

            return res

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    s = H*W + 1
    t = H*W + 2
    mcf = Mincostflow(H*W + 2)
    cnt = 0
    no_move = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                continue
            else:
                if grid[h][w] == "o":
                    cnt += 1
                    no_move += H + W - h - w
                    mcf.add_edge(s, h*W+w+1, 1, 0)
                if h+1 < H:
                    if grid[h+1][w] != "#":
                        mcf.add_edge(h*W+w+1, (h+1)*W+w+1, 100, 0)
                if w+1 < W:
                    if grid[h][w+1] != "#":
                        mcf.add_edge(h*W+w+1, h*W+w+2, 100, 0)
                mcf.add_edge(h*W+w+1, t, 1, H+W-h-w)
    print(no_move - mcf.flow(s, t, cnt))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

NUMERIC_LIMITS = (1 << 63) - 1
INF = 10 ** 9

class McfGraph:
  def __init__(self, n):
    self._n = n
    self.g = [[] for _ in range(n)]
    self.pos = []
 
  def add_edge(self, frm, to, cap, cost):
    m = len(self.pos)
    self.pos.append([frm, len(self.g[frm])])
    self.g[frm].append(self._edge(to, len(self.g[to]), cap, cost))
    self.g[to].append(self._edge(frm, len(self.g[frm]) - 1, 0, -cost))
    return m
 
  class edge:
    __slots__ = "frm", "to", "cap", "flow", "cost"
 
    def __init__(self, frm, to, cap, flow, cost):
      self.frm, self.to = frm, to
      self.cap, self.flow, self.cost = cap, flow, cost
 
  def get_edge(self, i):
    _e = self.g[self.pos[i][0]][self.pos[i][1]]
    _re = self.g[_e.to][_e.rev]
    return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)
 
  def edges(self):
    for i in range(len(self.pos)):
      yield self.get_edge(i)
 
  def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
    return self.slope(s, t, flow_limit)[-1]
 
  def dual_ref(self, s, t):
    dist = [NUMERIC_LIMITS] * self._n
    self.pv = [-1] * self._n
    self.pe = [-1] * self._n
    vis = [False] * self._n
    que = []
    dist[s] = 0
    heappush(que, (0, s))
    while que:
      _, v = heappop(que)
      if vis[v]:
        continue
      vis[v] = True
      if v == t:
        break
      for i in range(len(self.g[v])):
        e = self.g[v][i]
        if vis[e.to] or not e.cap:
          continue
        cost = e.cost - self.dual[e.to] + self.dual[v]
        if dist[e.to] - dist[v] > cost:
          dist[e.to] = dist[v] + cost
          self.pv[e.to] = v
          self.pe[e.to] = i
          heappush(que, (dist[e.to], e.to))
    if not vis[t]:
      return False
    for v in range(self._n):
      if not vis[v]:
        continue
      self.dual[v] -= dist[t] - dist[v]
    return True
 
  def slope(self, s, t, flow_limit=NUMERIC_LIMITS):
    self.dual = [0] * self._n
 
    flow = 0
    cost, prev_cost = 0, -1
    result = [(flow, cost)]
    while flow < flow_limit:
      if not self.dual_ref(s, t):
        break
      c = flow_limit - flow
      v = t
      while v != s:
        c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
        v = self.pv[v]
      v = t
      while v != s:
        e = self.g[self.pv[v]][self.pe[v]]
        e.cap -= c
        self.g[v][e.rev].cap += c
        v = self.pv[v]
      d = -self.dual[s]
      flow += c
      cost += c * d
      if prev_cost == d:
        result.pop()
      result.append((flow, cost))
      prev_cost = cost
    return result
 
  class _edge:
    __slots__ = "to", "rev", "cap", "cost"
 
    def __init__(self, to, rev, cap, cost):
      self.to, self.rev, self.cap, self.cost = to, rev, cap, cost
 
 
def atcoder_practice2_e():
    import sys
    input = sys.stdin.buffer.readline
 
    N, K = list(map(int, input().split()))
    A = [tuple(map(int, input().split())) for _ in range(N)]
    BIG = 10 ** 9
 
    g = McfGraph(2 * N + 2)
    s = 2 * N
    t = 2 * N + 1
 
    g.add_edge(s, t, N * K, BIG)
 
    for i in range(N):
        g.add_edge(s, i, K, 0)
        g.add_edge(N + i, t, K, 0)
    for i in range(N):
        for j in range(N):
            g.add_edge(i, N + j, 1, BIG - A[i][j])
 
    result = g.flow(s, t, N * K)
    print(N * K * BIG - result[1])
 
    grid = [["."] * N for _ in range(N)]
    edges = g.edges()
    for e in edges:
        if e.frm == s or e.to == t or e.flow == 0:
            continue
        grid[e.frm][e.to - N] = "X"
 
    for g in grid:
        print("".join(g))


N, M = map(int, input().split())
board = [input().strip() for i in range(N)]

g = McfGraph(M * N + 2)
s = M * N
t = M * N + 1

need = 0

for i in range(N):
    for j in range(M):
        if board[i][j] == 'o':
            need += 1
            g.add_edge(s, M * i + j, 1, i + j)

        if board[i][j] != '#':
            g.add_edge(M * i + j, t, 1, N + M - 2 - i - j)

            if i + 1 < N and board[i + 1][j] != '#':
                g.add_edge(M * i + j, M * (i + 1) + j, INF, 0)

            if j + 1 < M and board[i][j + 1] != '#':
                g.add_edge(M * i + j, M * i + j + 1, INF, 0)

flow, cost = g.flow(s, t, need)
opt = (N + M - 2) * need
print(opt - cost)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
V=N*M+2
INF=10**16
G=[[] for i in range(V)]
D=[INF]*V
PV,PE=[0]*V,[0]*V
def ae(fr,to,ca,co):
  global G
  G[fr].append([to,ca,co,len(G[to])])
  G[to].append([fr,0,-co,len(G[fr])-1])

def mcf(s,t,f):
  global G,V,INF,D,PV,PE
  r=0
  z=f
  while z>0:
    D=[INF]*V
    D[s]=0
    ud=True
    while ud:
      ud=False
      for x in range(V):
        if D[x]==INF:
          continue
        for i in range(len(G[x])):
          if G[x][i][1]>0 and D[G[x][i][0]]>D[x]+G[x][i][2]:
            D[G[x][i][0]]=D[x]+G[x][i][2]
            PV[G[x][i][0]]=x
            PE[G[x][i][0]]=i
            ud=True
    if D[t]==INF:
      return -(10**30)
    d=z
    x=t
    while x!=s:
      d=min(d,G[PV[x]][PE[x]][1])
      x=PV[x]
    z-=d
    r+=d*D[t]
    x=t
    while x!=s:
      G[PV[x]][PE[x]][1]-=d
      G[x][G[PV[x]][PE[x]][3]][1]+=d
      x=PV[x]
  return r

X=0
C=0
for i in range(N):
  for j in range(M):
    if S[i][j]=='#':
      continue
    ae(i*M+j,V-1,1,N+M-i-j)
    if S[i][j]=='o':
      C+=1
      X+=(N+M-i-j)
      ae(V-2,i*M+j,1,0)
    if i<N-1:
      if S[i+1][j]!='#':
        ae(i*M+j,i*M+M+j,INF,0)
    if j<M-1:
      if S[i][j+1]!='#':
        ae(i*M+j,i*M+1+j,INF,0)
print(X-mcf(V-2,V-1,C))

Submission status: Accepted

Solution code:
import sys
import networkx as nx
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())
S = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W].astype('U1')

INF = 1 << 32

total_o = (S == 'o').sum()
G = nx.DiGraph()
sink = 'sink'
G.add_node(sink, demand=total_o)
for i in range(H):
    for j in range(W):
        if S[i, j] == '#':
            continue
        if S[i, j] == 'o':
            G.add_node((i, j), demand=-1)
            G.add_edge((i, j), sink, capacity=1, weight=0)
        elif S[i, j] == '.':
            G.add_node((i, j), demand=0)
            G.add_edge((i, j), sink, capacity=1, weight=0)
        if i + 1 < H and S[i + 1, j] != '#':
            G.add_edge((i, j), (i + 1, j), capacity=INF, weight=-1)
        if j + 1 < W and S[i, j + 1] != '#':
            G.add_edge((i, j), (i, j + 1), capacity=INF, weight=-1)

mcfc = nx.min_cost_flow_cost(G)
ans = -mcfc
print(ans)

Submission status: Accepted

Solution code:
import networkx as nx

N, M = map(int, input().split())
S = [input() for _ in range(N)]
G = nx.MultiDiGraph()
cnt = 0
for s in S:
    cnt += s.count('o')
G.add_node('s', demand=-cnt)
G.add_node('t', demand=cnt)
for i in range(N):
    for j in range(M):
        if S[i][j] == '#':
            continue
        if S[i][j] == 'o':
            G.add_edge('s', M * i + j, weight=0, capacity=1)
        if j < M - 1 and S[i][j+1] != '#':
            G.add_edge(M * i + j, M * i + j + 1, weight=-1, capacity=10000)
        if i < N - 1 and S[i+1][j] != '#':
            G.add_edge(M * i + j, M * (i + 1) + j, weight=-1, capacity=10000)
        G.add_edge(M * i + j, 't', weight=0, capacity=1)
print(-nx.min_cost_flow_cost(G))

Submission status: Accepted

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

N,M=map(int,input().split())
MAP=[input().strip() for i in range(N)]

# vertex 0～N*M
# egg N*M～N*M+100
# start N*M+101
# goal N*M+102

start = N*M+101
goal = N*M+102
V=N*M+110
 
EDGE=[set() for i in range(V)]

EGGS=[]

for i in range(N):
    for j in range(M):
        if MAP[i][j]=="o":
            EGGS.append((i,j))

EGGNUM=len(EGGS)

for i in range(EGGNUM):
    x,y=EGGS[i]
    USE=[[0]*M for i in range(N)]
    Q=[(x,y)]

    while Q:
        x,y=Q.pop()
        EDGE[N*M+i].add(M*x+y)
        for z,w in [(x+1,y),(x,y+1)]:
            if 0<=z<N and 0<=w<M and USE[z][w]==0 and MAP[z][w]!="#":
                USE[z][w]=1
                Q.append((z,w))

for i in range(EGGNUM):
    EDGE[start].add(N*M+i)

for i in range(N):
    for j in range(M):
        if MAP[i][j]!="#":
            EDGE[M*i+j].add(goal)
 
BACK=[-1]*V
LA=0
 
import heapq
OVER=3000

def cost(x,y):
    #print(x,y)
    
    if N*M<=x<N*M+100 and y<N*M:
        z0,w0=EGGS[x-N*M]
        z1,w1=divmod(y,M)

        return 3000-(z1-z0+w1-w0)

    elif N*M<=y<N*M+100 and x<N*M:
        z0,w0=EGGS[y-N*M]
        z1,w1=divmod(x,M)

        return -(3000-(z1-z0+w1-w0))

    else:
        return 0
    
for flow in range(EGGNUM):
    ANS=[float("inf")]*V
    Q=[(0,start)]
    ANS[start]=0
 
    while Q:
        time,fr=heapq.heappop(Q)
        if time>ANS[fr]:
            continue
 
        for to in EDGE[fr]:
            c = cost(fr,to)
            if ANS[to]>ANS[fr]+c:
                ANS[to]=ANS[fr]+c
                BACK[to]=fr
                heapq.heappush(Q,(ANS[to],to))

    #print(ANS)
 
    LA+=ANS[goal]
 
    NOW=goal
    while NOW!=start:
        fr=BACK[NOW]
        EDGE[fr].remove(NOW)
        EDGE[NOW].add(fr)
 
        NOW=fr
 
print(3000*EGGNUM-LA)

Submission status: Accepted

Solution code:
import networkx as nx

n, m = map(int, input().split())

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, m)
cnt = 0
goal = (n, m + 1)

for i in range(n):
    for j in range(m):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < m:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(abs(ans))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/practice2/submissions/16805552 から拝借
# https://atcoder.jp/contests/acl1/submissions/16916932 を書き直し

import heapq

class mcf_graph_int_cost:
    """
    頂点数、及び、costの総和が、4294967295 (== (1 << 32) - 1) を超えない前提下での高速な実装。
    後者は超えても一応動く。
    """

    def __init__(self, n):
        self.n = n
        self.pos = []
        self.g = [[] for _ in range(n)]


    def add_edge(self, from_, to, cap, cost):
        # assert 0 <= from_ < self.n
        # assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((from_, len(self.g[from_])))
        self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap, cost))
        self.g[to].append(self.__class__._edge(from_, len(self.g[from_]) - 1, 0, -cost))
        return m


    class edge:
        def __init__(self, from_, to, cap, flow, cost):
            self.from_ = from_
            self.to = to
            self.cap = cap
            self.flow = flow
            self.cost = cost


    def get_edge(self, i):
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)


    def edges(self):
        ret = []
        for i in range(len(self.pos)):
            _e = self.g[self.pos[i][0]][self.pos[i][1]]
            _re = self.g[_e.to][_e.rev]
            ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
        return ret


    def _dual_ref(self):
            self.dist = [4294967295] * self.n
            self.pv = [-1] * self.n
            self.pe = [-1] * self.n
            self.vis = [False] * self.n

            que = [s]
            self.dist[s] = 0
            while que:
                v = heapq.heappop(que) & 4294967295
                if self.vis[v]:
                    continue
                self.vis[v] = True
                if v == t:
                    break
                for i in range(len(self.g[v])):
                    e = self.g[v][i]
                    if self.vis[e.to] or e.cap == 0:
                        continue
                    cost = e.cost - self.dual[e.to] + self.dual[v]
                    if self.dist[e.to] > self.dist[v] + cost:
                        self.dist[e.to] = self.dist[v] + cost
                        self.pv[e.to] = v
                        self.pe[e.to] = i
                        heapq.heappush(que, ((self.dist[e.to] << 32) + e.to))
            if not self.vis[t]:
                return False

            for v in range(self.n):
                if not self.vis[v]:
                    continue
                self.dual[v] -= self.dist[t] - self.dist[v]
            
            return True


    def slope(self, s, t, flow_limit=4294967295):
        # assert 0 <= s < self.n
        # assert 0 <= t < self.n
        # assert s != t
        
        self.dual = [0] * self.n
        self.dist = [4294967295] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n

        
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(flow, cost)]
        while flow < flow_limit:
            if not self._dual_ref():
                break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
                v = self.pv[v]
            v = t
            while v != s:
                e = self.g[self.pv[v]][self.pe[v]]
                e.cap -= c
                self.g[v][e.rev].cap += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result


    def flow(self, s, t, flow_limit=4294967295):
        return self.slope(s, t, flow_limit)[-1]

    
    class _edge:
        def __init__(self, to, rev, cap, cost):
            self.to = to
            self.rev = rev
            self.cap = cap
            self.cost = cost


from collections import deque
N, M = map(int, input().split())
X = [[0 if a == "#" else 1 if a == "." else 2 for a in input()] for _ in range(N)]

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (N * M)
    D[i0] = 0
    while Q:
        x = Q.popleft()
        i, j = x // M, x % M
        for di, dj in ((0, 1), (1, 0)):
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                if X[ni][nj]:
                    y = ni * M + nj
                    if D[y] == -1:
                        D[y] = D[x] + 1
                        Q.append(y)
    return D

E = []
ma = 0
for i in range(N):
    for j in range(M):
        if X[i][j] < 2: continue
        s = i * M + j
        b = BFS(s)
        for t in [a for a in range(N * M) if b[a] >= 0]:
            i2, j2 = t // M, t % M
            d = i2 - i + j2 - j
            ma = max(ma, d)
            E.append((s, t + N * M, d))
cnt = sum(sum([1 if a == 2 else 0 for a in x]) for x in X)

s = 2 * N * M
t = s + 1
g = mcf_graph_int_cost(t + 1)
for i in range(N):
    for j in range(M):
        if X[i][j] == 0: continue
        a = i*M+j+N*M
        if X[i][j] == 2:
            g.add_edge(s, i*M+j, 1, 0)
        g.add_edge(a, t, 1, 0)
for v, w, d in E:
    g.add_edge(v, w, 1, ma - d)

print(ma * cnt - g.flow(s, t, cnt)[1])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
s = [input() for _ in range(n)]
xys = []
# 最小費用流
"""nodeにdemand属性
edgeにcapacity, weight属性を指定
f以下の任意の流量について考えたければ、s->tにcapacity無限、weight=0の枝を追加すれば良い
"""
import networkx as nx
g = nx.DiGraph() # 必要に応じてMultiDiGraphにする
num = 0
for i in range(n):
    for j in range(m):
        u = i*m+j
        if s[i][j]=="o":
            num += 1
            g.add_node(u, demand=-1)
            xys.append(u)
        elif s[i][j]==".":
            g.add_node(u)
            xys.append(u)
        else:
            pass
        if i>=1:
            if s[i-1][j]!="#":
                v = (i-1)*m + j
                g.add_edge(v, u, capacity=100, weight=-1)
        if j>=1:
            if s[i][j-1]!="#":
                v = i*m + j-1
                g.add_edge(v, u, capacity=100, weight=-1)
g.add_node(n*m, demand=num)
for u in xys:
    g.add_edge(u,n*m,capacity=1,weight=0)
val, d = nx.network_simplex(g)
ans = -val
print(ans)

Submission status: Accepted

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

import heapq
pop,push=heapq.heappop,heapq.heappush

class mincf:
	inf=2*10**18
	
	class E:
		def __init__(self,to,cap,cost,nx):
			self.to=to
			self.cap=cap
			self.cost=cost
			self.nx=nx
			self.rev=None
	
	def __init__(self, n):
		self.n=n
		self.head=[None]*n
		self.h=[0]*n
		self.d=[0]*n
		self.pre=[None]*n
	
	def ae(self,a,b,cap,cost):
		head=self.head
		head[a]=self.E(b,cap,cost,head[a])
		head[b]=self.E(a,0,-cost,head[b])
		head[a].rev=head[b]
		head[b].rev=head[a]
	
	def go(self,s,t,f):
		inf=self.inf
		n=self.n
		head=self.head
		h=self.h
		d=self.d
		pre=self.pre
		pq=[(0,s)]
		
		d[0]=0
		d[1:]=[inf]*(n-1)
		while pq:
			(a,v)=pop(pq)
			if d[v]<a:
				continue
			if v==t:
				break
			
			e=head[v]
			while e is not None:
				if e.cap>0:
					w=d[v]+e.cost+h[v]-h[e.to]
					if w<d[e.to]:
						d[e.to]=w
						push(pq,(w,e.to))
						pre[e.to]=e
				e=e.nx
		
		if d[t]==inf:
			return (0,0)
		
		for i in range(n):
			h[i]=min(h[i]+min(d[i],d[t]),inf)
		
		a=f
		v=t
		while v!=s:
			a=min(a,pre[v].cap)
			v=pre[v].rev.to
		v=t
		while v!=s:
			x=pre[v]
			y=x.rev
			x.cap-=a
			y.cap+=a
			v=y.to
		
		return (a,h[t])
	
	def calc(self,s,t,f=None):
		if f is None:
			f=self.inf
		amount=0
		cost=0
		while f>0:
			a,c=self.go(s,t,f)
			if a==0:
				break
			amount+=a
			f-=a
			cost+=a*c
		return (amount,cost)

n,m=map(int,readline().split())
w=[readline().decode('utf-8') for _ in range(n)]
idx=[[-1]*m for _ in range(n)]

s=0
ps=[]

for i in range(n):
	for j in range(m):
		if w[i][j]=='o':
			ps.append((i,j))
		if w[i][j]!='#':
			idx[i][j]=s
			s+=1

ans=0
mcf=mincf(1+s+1)

for i,j in ps:
	ans+=n-i+m-j
	mcf.ae(0,1+idx[i][j],1,0)

for i in range(n):
	for j in range(m):
		if idx[i][j]!=-1:
			mcf.ae(1+idx[i][j],1+s,1,n-i+m-j)
			if i+1<n and idx[i+1][j]!=-1:
				mcf.ae(1+idx[i][j],1+idx[i+1][j],mcf.inf,0)
			if j+1<m and idx[i][j+1]!=-1:
				mcf.ae(1+idx[i][j],1+idx[i][j+1],mcf.inf,0)

f,cost=mcf.calc(0,1+s)
assert f==len(ps)
print(ans-cost)

Submission status: Runtime Error

Solution code:

import sys;input=sys.stdin.readline
from collections import deque, defaultdict
def encode(i, j):
    return 2 + K + i*M + j
from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def addEdge(self, fr, to, cap, cost):
#        print(fr, to, 10**18-cost)
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def minCostFlow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [None]*N

        d0 = [INF]*N
        dist = [INF]*N

        while f:
            dist[:] = d0
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                r0 = dist[v] + H[v]
                for e in G[v]:
                    w, cap, cost, _ = e
                    if cap > 0 and r0 + cost - H[w] < dist[w]:
                        dist[w] = r = r0 + cost - H[w]
                        prv_v[w] = v; prv_e[w] = e
                        heappush(que, (r, w))
            if dist[t] == INF:
                return None

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = prv_e[v]
                e[1] -= d
                e[3][1] += d
                v = prv_v[v]
        return res
N, M = map(int, input().split())
B = []
for _ in range(N):
    s = input().strip()
    B.append(s)

ks = []
for i in range(N):
    for j in range(M):
        if B[i][j] == "o":
            ks.append((i, j))
K = len(ks)
mcf = MinCostFlow(2+K+N*M)
for i in range(K):
    mcf.addEdge(0, i+2, 1, 0)

for ki in range(K):
    i, j = ks[ki]
    s = (i, j)
    queue=deque([s])
    vs = set([s])
    dist = defaultdict(int)
    while queue:
        u, v = queue.popleft()
#        print(2+ki, (u,v),encode(u,v), (i,j), dist[(u, v)])
        mcf.addEdge(2+ki, encode(u, v), 1, 10**18-dist[(u, v)])
        for nu, nv in [(u+1, v), (u, v+1)]:
            if (nu, nv) in vs:
                continue
            if nu >= N or nv >= M:
                continue
            if B[nu][nv] == "#":
                continue
            vs.add((nu, nv))
            queue.append((nu, nv))
            dist[(nu, nv)] = dist[(u, v)] + 1

for i in range(N):
    for j in range(M):
        mcf.addEdge(encode(i,j),1,1,0)
#print(mcf.G)
print(K*10**18-mcf.minCostFlow(0, 1, K))

Submission status: Runtime Error

Solution code:
from networkx import*
N, M = map(int, input().split())
X = [[0 if a == "#" else 1 if a == "." else 2 for a in input()] for _ in range(N)]
cnt = sum(sum([1 if a == 2 else 0 for a in x]) for x in X)
G = MultiDiGraph()
t = N * M
G.add_node(t, demand = cnt)
for i in range(N):
    for j in range(M):
        if X[i][j] == 0: continue
        a = i * M + j
        G.add_node(a, demand = 1 - X[i][j])
        G.add_edge(a, t, capacity = 1, weight = 0)
        if i + 1 < N and X[i+1][j]:
            b = a + M
            G.add_edge(a, b, capacity = N * M, weight = -1)
        if j + 1 < N and X[i][j+1]:
            b = a + 1
            G.add_edge(a, b, capacity = N * M, weight = -1)
print(-min_cost_flow_cost(G))