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: Time Limit Exceeded

Solution code:
import networkx as nx
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N, M = map(int, input().split())
    Sss = ['#'*(M+2)] + ['#'+input()+'#' for _ in range(N)] + ['#'*(M+2)]

    poss = []
    for i in range(1, N+1):
        for j in range(1, M+1):
            if Sss[i][j] == 'o':
                poss.append((i, j))

    numA = len(poss)

    def f(x, y):
        anss = []
        dp = [-INF]*(M+2)
        for i in range(1, N+1):
            dp2 = [-INF]*(M+2)
            for j in range(1, M+1):
                if Sss[i][j] == '#': continue
                if i == x and j == y:
                    dp2[j] = 0
                else:
                    dp2[j] = max2(dp[j], dp2[j-1]) + 1
            dp = dp2
            anss.append(dp[1:-1])
        return anss

    # for x, y in poss:
    #     f(x, y)
    #     print()

    s, t = N*M+numA, N*M+numA+1
    G = nx.DiGraph()
    G.add_node(s, demand=-numA)
    G.add_node(t, demand=numA)
    for i in range(N):
        for j in range(M):
            k = i*M+j
            G.add_node(k)
            G.add_edge(k, t, weight=0, capacity=1)

    KK = 10**6
    for iPos, (x, y) in enumerate(poss, start=N*M):
        G.add_node(iPos)
        G.add_edge(s, iPos, weight=0, capacity=1)
        dp = f(x, y)
        for i in range(N):
            for j in range(M):
                if dp[i][j] != -INF:
                    k = i*M+j
                    wt = KK - dp[i][j]
                    G.add_edge(iPos, k, weight=wt, capacity=1)

    C = nx.min_cost_flow_cost(G)
    ans = KK*numA - C
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N, M = map(int, input().split())
    Sss = ['#'*(M+2)] + ['#'+input()+'#' for _ in range(N)] + ['#'*(M+2)]

    poss = []
    for i in range(1, N+1):
        for j in range(1, M+1):
            if Sss[i][j] == 'o':
                poss.append((i, j))

    numA = len(poss)

    def f(x, y):
        dp = [[-INF]*(M+2) for _ in range(N+2)]
        for i in range(1, N+1):
            for j in range(1, M+1):
                if Sss[i][j] == '#': continue
                if i == x and j == y:
                    dp[i][j] = 0
                else:
                    dp[i][j] = max2(dp[i-1][j], dp[i][j-1]) + 1
    #        print(dp[i])
        return dp

    # for x, y in poss:
    #     f(x, y)
    #     print()

    s, t = N*M+numA, N*M+numA+1
    G = nx.DiGraph()
    G.add_node(s, demand=-numA)
    G.add_node(t, demand=numA)
    for i in range(N):
        for j in range(M):
            k = i*M+j
            G.add_node(k)
            G.add_edge(k, t, weight=0, capacity=1)

    KK = 10**6
    for iPos, (x, y) in enumerate(poss, start=N*M):
        G.add_node(iPos)
        G.add_edge(s, iPos, weight=0, capacity=1)
        dp = f(x, y)
        for i in range(1, N+1):
            for j in range(1, M+1):
                if dp[i][j] != -INF:
                    k = (i-1)*M+j-1
                    wt = KK - dp[i][j]
                    G.add_edge(iPos, k, weight=wt, capacity=1)

    C = nx.min_cost_flow_cost(G)
    ans = KK*numA - C
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N, M = map(int, input().split())
    Sss = ['#'*(M+2)] + ['#'+input()+'#' for _ in range(N)] + ['#'*(M+2)]

    poss = []
    for i in range(1, N+1):
        for j in range(1, M+1):
            if Sss[i][j] == 'o':
                poss.append((i, j))

    numA = len(poss)

    def f(x, y):
        dp = [[-INF]*(M+2) for _ in range(N+2)]
        for i in range(1, N+1):
            for j in range(1, M+1):
                if Sss[i][j] == '#': continue
                if i == x and j == y:
                    dp[i][j] = 0
                else:
                    dp[i][j] = max2(dp[i-1][j], dp[i][j-1]) + 1
    #        print(dp[i])
        return dp

    # for x, y in poss:
    #     f(x, y)
    #     print()

    s, t = N*M+numA, N*M+numA+1
    G = nx.DiGraph()
    G.add_node(s, demand=-numA)
    G.add_node(t, demand=numA)
    for i in range(N):
        for j in range(M):
            k = i*M+j
            G.add_node(k)
            G.add_edge(k, t, weight=0, capacity=1)

    KK = 10**6
    for iPos, (x, y) in enumerate(poss, start=N*M):
        G.add_node(iPos)
        G.add_edge(s, iPos, weight=0, capacity=1)
        dp = f(x, y)
        for i in range(1, N+1):
            for j in range(1, M+1):
                if dp[i][j] != -INF:
                    k = (i-1)*M+j-1
                    wt = KK - dp[i][j]
                    G.add_edge(iPos, k, weight=wt, capacity=1)

    C = nx.min_cost_flow_cost(G)
    ans = KK*numA - C
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k 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 = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def build_grid(H, W, intv, _type, space=False, padding=True):
    # 入力がスペース区切りかどうか
    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

class MinCostFlow:
    """ 最小費用流(ベルマンフォード版、負コストに対応可)：O(F*E*V) """

    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.pos = []
    
    def copy(self):
        res = MinCostFlow(self.N)
        res.G = [[a[:] for a in b] for b in self.G]
        res.pos = [a[:] for a in self.pos]
        return res

    def add_edge(self, fr, to, cap, cost):
        self.pos.append((fr, len(self.G[fr])))
        self.G[fr].append([to, cap, cost, len(self.G[to])])
        self.G[to].append([fr, 0, -cost, len(self.G[fr])-1])

    def flow(self, s, t, f):

        N = self.N; G = self.G
        INF = MinCostFlow.INF

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

        while f:
            dist = [INF] * N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF:
                        continue
                    for i, (to, cap, cost, _) in enumerate(G[v]):
                        if cap > 0 and dist[to] > dist[v] + cost:
                            dist[to] = dist[v] + cost
                            prv_v[to] = v; prv_e[to] = i
                            update = True
            if dist[t] == INF:
                return INF

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

    def get_edge(self, i):
        e = self.G[self.pos[i][0]][self.pos[i][1]]
        re = self.G[e[0]][e[3]]
        # from, to, cap, flow, cost
        return (self.pos[i][0], e[0], e[1]+re[1], re[1], e[2])

    def get_edges(self):
        M = len(self.pos)
        res = []
        for i in range(M):
            res.append(self.get_edge(i))
        return res

N, M = MAP()
grid = build_grid(N, M, '#', str)
N += 2
M += 2

cnt = 0
for i in range(1, N):
    for j in range(1, M):
        if grid[i][j] == 'o':
            cnt += 1
mcf = MinCostFlow(N*M+2)
s = N*M
t = N*M+1
MX = cnt

directions = ((1, 0), (0, 1))
for i in range(1, N):
    for j in range(1, M):
        if grid[i][j] == 'o':
            mcf.add_edge(s, i*M+j, 1, 0)
        if grid[i][j] in ['o', '.']:
            mcf.add_edge(i*M+j, t, 1, 0)
            for di, dj in directions:
                ni, nj = i+di, j+dj
                if grid[ni][nj] in ['o', '.']:
                    mcf.add_edge(i*M+j, ni*M+nj, MX, -1)

ans = -mcf.flow(s, t, MX)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

INF = 10 ** 18

class Edge():
    def __init__(self, fr, to, capacity, cost):
        self.fr = fr
        self.to = to
        self.capacity = capacity
        self.cost = cost

    def __str__(self):
        return "fr: {}, to: {}, cap: {}, cost: {}".format(self.fr, self.to,
                self.capacity, self.cost)


class MCF():
    def __init__(self, n, edges):
        self.edges = edges
        self.n = n

    def shortest_paths(self, v0):
        d = [INF] * self.n
        p = [-1] * self.n
        d[v0] = 0
        m = [2] * self.n
        q = collections.deque()
        q.append(v0)

        while len(q) > 0:
            u = q.popleft()
            m[u] = 0;
            for v in self.adj[u]:
                if self.capacity[u][v] > 0 and \
                        d[v] > d[u] + self.cost[u][v]:
                    d[v] = d[u] + self.cost[u][v]
                    p[v] = u
                    if m[v] == 2:
                        m[v] = 1
                        q.append(v)
                    elif m[v] == 0:
                        m[v] = 1
                        q.appendleft(v)

        return d, p

    def min_cost_flow(self, desired_flow, s, t):
        self.adj = [[]] * self.n
        self.cost = [[0] * self.n for i in range(self.n)]
        self.capacity = [[0] * self.n for i in range(self.n)]

        for e in self.edges:
            self.adj[e.fr].append(e.to)
            self.adj[e.to].append(e.fr)
            self.cost[e.fr][e.to] = e.cost
            self.cost[e.to][e.fr] = -e.cost
            self.capacity[e.fr][e.to] = e.capacity

        flow, cost = 0, 0
        d, p = [], []
        while flow < desired_flow:
            d, p = self.shortest_paths(s)
            if d[t] == INF:
                break

            f = desired_flow - flow
            cur = t
            while cur != s:
                f = min(f, self.capacity[p[cur]][cur])
                cur = p[cur]

            flow += f
            cost += f * d[t]
            cur = t
            while cur != s:
                self.capacity[p[cur]][cur] -= f
                self.capacity[cur][p[cur]] += f
                cur = p[cur]

            #print(" :: ", flow)

        return flow, cost;


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

nodes = N * M + 2
s = nodes - 1
t = nodes - 2
edges = []
need = 0

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

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

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

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

st = MCF(nodes, edges)
flow, cost = st.min_cost_flow(need, s, t)
opt = (N + M - 2) * need
print(opt - cost)

Submission status: Time Limit Exceeded

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

from networkx import*
G = MultiDiGraph()
t = 2 * N * M
G.add_node(t, demand = cnt)
for i in range(N):
    for j in range(M):
        if X[i][j] == 0: continue
        if X[i][j] == 2:
            G.add_node(i*M+j, demand = -1)
        a = i*M+j+N*M
        G.add_node(a, demand = 0)
        G.add_weighted_edges_from([(a, t, 0)], capacity = 1)
G.add_weighted_edges_from([(v, w, ma - d) for v, w, d in E], capacity = 1)
print(ma * cnt - min_cost_flow_cost(G))

Submission status: Accepted

Solution code:
import networkx as nx

n,m=map(int,input().split())
board=[input() for _ in range(n)]
k=0
for i in range(n):
  for j in range(m):
    if board[i][j]=='o':
      k+=1
INF=10**9
g=nx.DiGraph()
g.add_node(0,demand=k)
for i in range(n):
  for j in range(m):
    if board[i][j]=='#':
      continue
    if board[i][j]=='o':
      g.add_node((i,j),demand=-1)
      g.add_edge((i,j),0,capacity=1,weight=0)
    elif board[i][j]=='.':
      g.add_node((i,j),demand=0)
      g.add_edge((i,j),0,capacity=1,weight=0)
    if i+1<n and board[i+1][j]!='#':
      g.add_edge((i,j),(i+1,j),weight=-1,capacity=INF)
    if j+1<m and board[i][j+1]!='#':
      g.add_edge((i,j),(i,j+1),weight=-1,capacity=INF)
flow=nx.min_cost_flow(g)
result=sum(v*g[k1][k2]['weight'] for k1,dc in flow.items() for k2,v in dc.items())
print(-result)

Submission status: Accepted

Solution code:
# Reference: https://tjkendev.github.io/procon-library/python/min_cost_flow/primal-dual.html
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 add_edge(self, fr, to, cap, cost):
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def flow(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

###

from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n, m = map(int, input().split())
    s = [input() for _ in range(n)]

    mcf = MinCostFlow(n*m + 2)

    source = n * m
    sink = n * m + 1

    ans = 0
    cnt = 0
    for i in range(n):
        for j in range(m):
            if s[i][j] == '#':
                continue

            ind = m * i + j

            # source >>> 'o'
            if s[i][j] == 'o':
                ans -= i + j
                cnt += 1
                mcf.add_edge(source, ind, 1, 0)

            mcf.add_edge(ind, sink, 1, -i-j)

            if i < n - 1 and s[i+1][j] != '#':
                mcf.add_edge(ind, m*(i+1) + j, 100, 0)
            if j < m - 1 and s[i][j+1] != '#':
                mcf.add_edge(ind, m*i + j+1, 100, 0)

    print(ans - mcf.flow(source, sink, cnt))

main()

Submission status: Accepted

Solution code:
import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(n, m, field):
    MINCOSTFLOW_LINKS = []
    INF = 10 ** 18

    def mincostflow_init(n):
        """ n: 頂点数 """
        lst = [[0]]
        lst.clear()
        MINCOSTFLOW_LINKS.append([lst.copy() for _ in range(n)])
        return len(MINCOSTFLOW_LINKS) - 1

    def mincostflow_add_link(ins, frm, to, capacity, cost):
        """ インスタンスID, 辺始点頂点番号, 辺終点頂点番号, 容量, コスト """
        links = MINCOSTFLOW_LINKS[ins]
        links[frm].append([to, capacity, cost, len(links[to])])
        links[to].append([frm, 0, -cost, len(links[frm]) - 1])

    def mincostflow_flow(ins, s, t, quantity):
        """ インスタンスID, フロー始点頂点番号, フロー終点頂点番号, 要求流量 """
        links = MINCOSTFLOW_LINKS[ins]
        n = len(links)
        res = 0
        potentials = np.zeros(n, dtype=np.int64)
        dist = np.full(n, INF, dtype=np.int64)
        prev_v = np.full(n, -1, dtype=np.int64)
        prev_e = np.full(n, -1, dtype=np.int64)

        while quantity:
            dist.fill(INF)
            dist[s] = 0
            que = [(0, s)]

            while que:
                total_cost, v = heappop(que)
                if dist[v] < total_cost:
                    continue
                for i, (u, cap, cost, _) in enumerate(links[v]):
                    new_cost = dist[v] + potentials[v] - potentials[u] + cost
                    if cap > 0 and new_cost < dist[u]:
                        dist[u] = new_cost
                        prev_v[u] = v
                        prev_e[u] = i
                        heappush(que, (new_cost, u))

            # Cannot flow quantity
            if dist[t] == INF:
                return -1

            potentials += dist

            cur_flow = quantity
            v = t
            while v != s:
                cur_flow = min(cur_flow, links[prev_v[v]][prev_e[v]][1])
                v = prev_v[v]
            quantity -= cur_flow
            res += cur_flow * potentials[t]

            v = t
            while v != s:
                link = links[prev_v[v]][prev_e[v]]
                link[1] -= cur_flow
                links[v][link[3]][1] += cur_flow
                v = prev_v[v]

        return res

    nm = (n + 2) * (m + 2)
    m2 = m + 2

    starts = np.where(field == 1)[0]
    s_size = starts.size

    ins = mincostflow_init(nm + 2)
    s = nm
    t = s + 1

    for i in starts:
        x, y = divmod(i, m2)
        mincostflow_add_link(ins, s, i, 1, x + y - 2)

    for i in range(nm):
        if field[i] == 2:
            continue
        x, y = divmod(i, m2)
        mincostflow_add_link(ins, i, t, 1, n + m - x - y)
        if field[i + 1] != 2:
            mincostflow_add_link(ins, i, i + 1, INF, 0)
        if field[i + m2] != 2:
            mincostflow_add_link(ins, i, i + m2, INF, 0)

    f = mincostflow_flow(ins, s, t, s_size)

    ans = (n + m - 2) * s_size - f
    return ans


SIGNATURE = '(i8,i8,i1[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n, m = map(int, sys.stdin.readline().split())
field = '#' * (m + 3) + '##'.join(sys.stdin.read().split()) + '#' * (m + 3)
field = np.fromiter(map('.o#'.index, field), np.int8)
ans = solve(n, m, field)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(n, m, field):
    MINCOSTFLOW_LINKS = []
    INF = 10 ** 18

    def mincostflow_init(n):
        """ n: 頂点数 """
        lst = [[0]]
        lst.clear()
        MINCOSTFLOW_LINKS.append([lst.copy() for _ in range(n)])
        return len(MINCOSTFLOW_LINKS) - 1

    def mincostflow_add_link(ins, frm, to, capacity, cost):
        """ インスタンスID, 辺始点頂点番号, 辺終点頂点番号, 容量, コスト """
        links = MINCOSTFLOW_LINKS[ins]
        links[frm].append([to, capacity, cost, len(links[to])])
        links[to].append([frm, 0, -cost, len(links[frm]) - 1])

    def mincostflow_flow(ins, s, t, quantity):
        """ インスタンスID, フロー始点頂点番号, フロー終点頂点番号, 要求流量 """
        links = MINCOSTFLOW_LINKS[ins]
        n = len(links)
        res = 0
        potentials = np.zeros(n, dtype=np.int64)
        dist = np.full(n, INF, dtype=np.int64)
        prev_v = np.full(n, -1, dtype=np.int64)
        prev_e = np.full(n, -1, dtype=np.int64)

        while quantity:
            dist.fill(INF)
            dist[s] = 0
            que = [(0, s)]

            while que:
                total_cost, v = heappop(que)
                if dist[v] < total_cost:
                    continue
                for i, (u, cap, cost, _) in enumerate(links[v]):
                    new_cost = dist[v] + potentials[v] - potentials[u] + cost
                    if cap > 0 and new_cost < dist[u]:
                        dist[u] = new_cost
                        prev_v[u] = v
                        prev_e[u] = i
                        heappush(que, (new_cost, u))

            # Cannot flow quantity
            if dist[t] == INF:
                return -1

            potentials += dist

            cur_flow = quantity
            v = t
            while v != s:
                cur_flow = min(cur_flow, links[prev_v[v]][prev_e[v]][1])
                v = prev_v[v]
            quantity -= cur_flow
            res += cur_flow * potentials[t]

            v = t
            while v != s:
                link = links[prev_v[v]][prev_e[v]]
                link[1] -= cur_flow
                links[v][link[3]][1] += cur_flow
                v = prev_v[v]

        return res

    nm = (n + 2) * (m + 2)
    m2 = m + 2

    starts = np.where(field == 1)[0]
    s_size = starts.size

    ins = mincostflow_init(nm + 2)
    s = nm
    t = s + 1

    POTENCIAL = 10000

    for i in starts:
        x, y = divmod(i, m2)
        mincostflow_add_link(ins, s, i, 1, (x + y - 2) * POTENCIAL)

    for i in range(nm):
        if field[i] == 2:
            continue
        x, y = divmod(i, m2)
        mincostflow_add_link(ins, i, t, 1, (n + m - x - y) * POTENCIAL)
        if field[i + 1] != 2:
            mincostflow_add_link(ins, i, i + 1, INF, POTENCIAL - 1)
        if field[i + m2] != 2:
            mincostflow_add_link(ins, i, i + m2, INF, POTENCIAL - 1)

    f = mincostflow_flow(ins, s, t, s_size)

    ans = (n + m - 2) * POTENCIAL * s_size - f
    return ans


SIGNATURE = '(i8,i8,i1[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    # solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n, m = map(int, sys.stdin.readline().split())
field = '#' * (m + 3) + '##'.join(sys.stdin.read().split()) + '#' * (m + 3)
field = np.fromiter(map('.o#'.index, field), np.int8)
ans = solve(n, m, field)
print(ans)

Submission status: Accepted

Solution code:
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):
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def flow(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

G=MinCostFlow(2502)
n,m=map(int,input().split())
S=[]
for _ in range(n):
    S.append(input())
    
os=0

for i in range(n):
    for q in range(m):
        cnt=i*m+q+1
        now=S[i][q]
        if now=="#":
            continue
        if now=="o":
            G.addEdge(0,cnt,1,0)
            os+=1
        if q<m-1 and S[i][q+1]!="#":
            G.addEdge(cnt,cnt+1,1000,-1)
        if i<n-1 and S[i+1][q]!="#":
            G.addEdge(cnt,cnt+m,1000,-1)
        G.addEdge(cnt,2501,1,0)

ans=G.flow(0,2501,os)
print(-ans)