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: Wrong Answer

Solution code:
code = r'''
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector
from libcpp.pair cimport pair
cdef extern from *:
    ctypedef int MOD '998244353'
    ctypedef long long ll 'long long'
#
cdef extern from '<atcoder/fenwicktree>' namespace 'atcoder':
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, ll x): self.ptr.add(p, x)
    cpdef ll sum(self, int l, int r): return self.ptr.sum(l, r)
#
cdef extern from '<atcoder/string>' namespace 'atcoder':
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[ll] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[ll] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[ll] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[ll] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[ll] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[ll] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)
#
cdef extern from '<atcoder/math>' namespace 'atcoder':
    ll pow_mod(ll x, ll n, ll m)
    ll inv_mod(ll x, ll m)
    pair[ll, ll] crt(vector[ll] r, vector[ll] m)
    ll floor_sum(ll n, ll m, ll a, ll b)
cpdef ll pow_mod_(ll x, ll n, ll m): return pow_mod(x, n, m)
cpdef ll inv_mod_(ll x, ll m): return inv_mod(x, m)
cpdef pair[ll, ll] crt_(vector[ll] r, vector[ll] m): return crt(r, m)
cpdef ll floor_sum_(ll n, ll m, ll a, ll b): return floor_sum(n, m, a, b)
#
cdef extern from '<atcoder/convolution>' namespace 'atcoder':
    vector[ll] convolution[m](vector[ll] a, vector[ll] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef vector[ll] convolution_(vector[ll] a, vector[ll] b): return convolution[MOD](a, b)
cpdef vector[ll] convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)
#
cdef extern from '<atcoder/dsu>' namespace 'atcoder':
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()
#
cdef extern from '<atcoder/maxflow>' namespace 'atcoder':
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm 'from', to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[ll] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap): return self.ptr.add_edge(frm, to, cap)
    cpdef ll flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef ll flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[ll] get_edge(self, int i):
        cdef mf_graph[ll].edge *e = new mf_graph[ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()		
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mf_graph[ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, ll new_cap, ll new_flow): self.ptr.change_edge(i, new_cap, new_flow)
#
cdef extern from '<atcoder/mincostflow>' namespace 'atcoder':
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int frm, int to, Cap cap, Cost cost)
        pair[Cap, Cost] flow(int s, int t)
        pair[Cap, Cost] flow(int s, int t, Cap flow_limit)
        vector[pair[Cap, Cost]] slope(int s, int t)
        vector[pair[Cap, Cost]] slope(int s, int t, Cap flow_limit)
        cppclass edge:
            int frm 'from', to
            Cap cap, flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
cdef class mcf_graph_:
    cdef mcf_graph[ll, ll] *ptr
    def __cinit__(self, int n): self.ptr = new mcf_graph[ll, ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap, ll cost): return self.ptr.add_edge(frm, to, cap, cost)
    cpdef pair[ll, ll] flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef pair[ll, ll] flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[pair[ll, ll]] slope(self, int s, int t): return self.ptr.slope(s, t)
    cpdef vector[pair[ll, ll]] slope_limit(self, int s, int t, ll flow_limit): return self.ptr.slope(s, t, flow_limit)
    cpdef vector[ll] get_edge(self, int i):
        cdef mcf_graph[ll, ll].edge *e = new mcf_graph[ll, ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        ret_e.push_back(e.cost)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mcf_graph[ll, ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
            ret_es.at(i).push_back(es.at(i).cost)
        return ret_es[0]
#
cdef extern from '<atcoder/scc>' namespace 'atcoder':
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
cdef class scc_graph_:
    cdef scc_graph *ptr
    def __cinit__(self, int n): self.ptr = new scc_graph(n)  
    def __dealloc__(self): del self.ptr
    cpdef void add_edge(self, int fr, int to): self.ptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self): return self.ptr.scc()
#
cdef extern from '<atcoder/twosat>' namespace 'atcoder':
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()
cdef class two_sat_:
    cdef two_sat *ptr
    def __cinit__(self, int n): self.ptr = new two_sat(n)
    def __dealloc__(self): del self.ptr
    cpdef void add_clause(self, int i, bool f, int j, bool g): self.ptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self): return self.ptr.satisfiable()
    cpdef vector[bool] answer(self): return self.ptr.answer()
'''
import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
g=mcf_graph_(N*M+2)
s,t=N*M,N*M+1
X=10**9
for i in range(N):
    for j in range(M):
        if S[i][j]=='o':
            g.add_edge(s,i*M+j,1,X)
        if j<M-1 and S[i][j]!='#'!=S[i][j+1]:
            g.add_edge(i*M+j,i*M+j+1,X,-1)
        if i<N-1 and S[i][j]!='#'!=S[i+1][j]:
            g.add_edge(i*M+j,(i+1)*M+j,X,-1)
        g.add_edge(i*M+j,t,1,M)
g.flow(s,t)
print(sum([e[3] for e in g.edges() if e[0]!=s and e[1]!=t and e[3]]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = [list(input()) for i in range(N)]

from collections import deque
ans = 0
for i in range(N-1,-1,-1):
    for j in range(M-1,-1,-1):
        if S[i][j] != 'o': continue
        q = deque([(i,j,0)])
        md = my = mx = 0
        while q:
            y,x,d = q.popleft()
            if d > md:
                md = d
                my = y
                mx = x
            elif d == md and y > my:
                my = y
                mx = x
            for dx,dy in [(0,1),(1,0)]:
                nx,ny = x+dx,y+dy
                if not 0 <= nx < M: continue
                if not 0 <= ny < N: continue
                if S[ny][nx] != '.': continue
                q.append((ny,nx,d+1))
        ans += md
        S[i][j] = '.'
        S[my][mx] = 'o'
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
grid = []
for i in range(N):
	grid.append(list(rs()))
#print(grid)

def moves(i, j):
	queue = deque([(i,j,0)])
	max_level = -1
	max_i, max_j = -1, -1
	while queue:
		i, j, level = queue.popleft()
		for di, dj in [(1, 0), (0, 1)]:
			ni, nj = i+di, j+dj
			#print(ni,nj)
			if 0 <= ni < N and 0 <= nj < M:
				if grid[ni][nj] in ['o', '#']:
					continue
				queue.append((ni, nj, level+1))
				if max_level < level+1:
					max_level = level+1
					max_i = ni
					max_j = nj
	return max_i, max_j, max_level

ans = 0
for i in range(N-1, -1, -1):
	for j in range(M-1, -1, -1):
		if grid[i][j] != 'o':
			continue
		ni, nj, nl = moves(i, j)
		ans += nl
		grid[i][j] = '.'
		grid[ni][nj] = 'o'
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n,m=LI()
s=SRL(n)
pos=[]
for i in range(n-1,-1,-1):
    for j in range(m-1,-1,-1):
        if s[i][j]=="o":
            pos+=[(i,j)]

ans=0

for k in range(len(pos)):
    y,x=pos[k]
    grid=[[0]*m for _ in range(n)]
    grid[y][x]=1
    q=deque([(y,x,0)])
    ret=0
    s[y][x]="."
    fy,fx=y,x
    while q:
        cy,cx,l=q.popleft()
        for g,h in ((1,0),(0,1)):
            ny=cy+g
            nx=cx+h
            if 0<=ny<n and 0<=nx<m and s[ny][nx]=="." and not grid[ny][nx]:
                grid[ny][nx]=1
                q+=[(ny,nx,l+1)]
                ret=l+1
                fy,fx=ny,nx
            elif 0 <= ny < n and 0 <= nx < m and s[ny][nx] == "o" and not grid[ny][nx]:
                grid[ny][nx] = 1
                q += [(ny, nx, l + 1)]
    ans+=ret
    s[fy][fx]="o"


pprint(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n,m=LI()
s=SRL(n)
pos=[]
for i in range(n-1,-1,-1):
    for j in range(m-1,-1,-1):
        if s[i][j]=="o":
            pos+=[(i,j)]

ans=0

for k in range(len(pos)):
    y,x=pos[k]
    grid=[[0]*m for _ in range(n)]
    grid[y][x]=1
    q=deque([(y,x,0)])
    ret=0
    s[y][x]="."

    while q:
        cy,cx,l=q.popleft()
        for g,h in ((1,0),(0,1)):
            ny=cy+g
            nx=cx+h
            if 0<=ny<n and 0<=nx<m and s[ny][nx]=="." and not grid[ny][nx]:
                grid[ny][nx]=1
                q+=[(ny,nx,l+1)]
    ans+=l
    s[cy][cx]="#"


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n,m=LI()
s=SRL(n)
pos=[]
for i in range(n-1,-1,-1):
    for j in range(m-1,-1,-1):
        if s[i][j]=="o":
            pos+=[(i,j)]

ans=0

for k in range(len(pos)):
    y,x=pos[k]
    if y==6 and x==1:
        print(1)
    grid=[[0]*m for _ in range(n)]
    grid[y][x]=1
    q=deque([(y,x,0)])
    ret=0
    s[y][x]="."

    while q:
        cy,cx,l=q.popleft()
        for g,h in ((1,0),(0,1)):
            ny=cy+g
            nx=cx+h
            if 0<=ny<n and 0<=nx<m and s[ny][nx]=="." and not grid[ny][nx]:
                grid[ny][nx]=1
                q+=[(ny,nx,l+1)]
    ans+=l
    s[cy][cx]="#"


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque
N, M = map(int, input().split())
grid = [input() for _ in range(N)]


class MCF_graph(object):
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]  # to, rev, cap, cost
        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([to, len(self.g[to]), cap, cost])
        self.g[to].append([frm, len(self.g[frm]) - 1, 0, -cost])
        return m

    def __get_edge(self, i):
        e_to, e_rev, e_cap, e_cost = self.g[self.pos[i][0]][self.pos[i][1]]
        re_to, _, re_cap, _ = self.g[e_to][e_rev]
        # from, to, cap, flow, cost
        return (re_to, e_to, e_cap + re_cap, re_cap, e_cost)

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.__get_edge(i)

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

    def slope(self, s, t, flow_limit=10**18):
        dual = [0] * self.n
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(0, 0)]  # cap, cost
        while flow < flow_limit:
            # call dual_ref()
            dist = [10**18] * self.n
            pv = [-1] * self.n
            pe = [-1] * self.n
            vis = [False] * self.n
            dist[s] = 0
            que = [(0, s)]
            while que:
                _, v = heapq.heappop(que)
                if vis[v]:
                    continue
                vis[v] = True
                if v == t:
                    break
                for i, (e_to, _, e_cap, e_cost) in enumerate(self.g[v]):
                    if vis[e_to] or (not e_cap):
                        continue
                    tmp_cost = e_cost - dual[e_to] + dual[v]
                    if dist[e_to] > dist[v] + tmp_cost:
                        dist[e_to] = dist[v] + tmp_cost
                        pv[e_to] = v
                        pe[e_to] = i
                        heapq.heappush(que, (dist[e_to], e_to))
            if not vis[t]:
                break
            for v, visited in enumerate(vis):
                if not visited:
                    continue
                dual[v] -= dist[t] - dist[v]
            # end dual_ref()

            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.g[pv[v]][pe[v]][2])
                v = pv[v]
            v = t
            while v != s:
                i, j = pv[v], pe[v]
                self.g[i][j][2] -= c
                self.g[v][self.g[i][j][1]][2] += c
                v = i
            d = -dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result


g = MCF_graph(N * M + 2)
source = N * M
sink = N * M + 1


inf = 10**18
piece = 0
for i in range(N):
    for j in range(M):
        g.add_edge(i * M + j, sink, 1, 0)
        if grid[i][j] == "o":
            piece += 1
            # bfs
            v = i * M + j
            g.add_edge(source, v, 1, 0)

            dist = [[inf]*M for _ in range(N)]
            dist[i][j] = 0
            node = deque([(i, j)])
            while node:
                i, j = node.popleft()
                if i + 1 < N and grid[i + 1][j] != "#":
                    vv = (i + 1) * M + j
                    dist[i+1][j] = dist[i][j] + 1
                    g.add_edge(v, vv, 1, dist[i + 1][j])
                    node.append((i + 1, j))
                if j + 1 < M and grid[i][j + 1] != "#":
                    vv = i * M + j + 1
                    dist[i][j+1] = dist[i][j] + 1
                    g.add_edge(v, vv, 1, dist[i][j + 1])
                    node.append((i, j + 1))

flow, cost = g.flow(source, sink, piece)
print(flow * 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq


class PrimalDual:
    def __init__(self, n: int):
        """頂点数をnとする。"""
        self.INF = 10 ** 18
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, _from: int, to: int, capacity: int, cost: int):
        """辺を追加
        1. _fromからtoへ向かう容量capacity、単位コストcostの辺をグラフに追加する。
        2. toから_fromへ向かう容量0、単位コスト-costの辺をグラフに追加する。
        """
        forward = [to, capacity, cost, None]
        forward[3] = backward = [_from, 0, -cost, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)

    def min_cost_flow(self, s: int, t: int, f: int) -> int:
        """s-tパス上に流量fを流すときの最小費用流を求める。
        計算量: O(|F||E|log|V|)
        """
        res = 0
        potential = [0] * self.n
        prv_v = [0] * self.n
        prv_e = [None] * self.n
        while f > 0:
            # ポテンシャルを用いたダイクストラ法
            dist = [self.INF] * self.n
            dist[s] = 0
            q = [(0, s)]  # q = [(sからのコスト, 現在地)]
            while q:
                cost, _from = heapq.heappop(q)
                if dist[_from] < cost:
                    continue
                for edge in self.graph[_from]:
                    to, capacity, cost, _ = edge
                    p_diff = potential[_from] - potential[to]
                    if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
                        dist[to] = dist[_from] + cost + p_diff
                        prv_v[to] = _from
                        prv_e[to] = edge
                        heapq.heappush(q, (dist[to], to))

            if dist[t] == self.INF:
                return -1
            for i in range(self.n):
                if dist[i] != self.INF:
                    potential[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += potential[t] * d
            v = t
            while v != s:
                edge = prv_e[v]
                edge[1] -= d
                edge[3][1] += d
                v = prv_v[v]
        return res


n, m = map(int, input().split())
s = [input() for i in range(n)]
OFFSET = 10 ** 5


def bfs(i, j, cnt):
    q = deque([(i, j)])
    dist = [[OFFSET] * m for i in range(n)]
    dist[i][j] = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (0, 1)):
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < n and 0 <= nxt_j < m):
                continue
            if s[nxt_i][nxt_j] == "#":
                continue
            if dist[nxt_i][nxt_j] != OFFSET:
                continue
            dist[nxt_i][nxt_j] = dist[i][j] + 1
            q.append((nxt_i, nxt_j))
    # o -> goal
    pd.add_edge(n * m + cnt, goal, 1, 0)
    for i in range(n):
        for j in range(m):
            if dist[i][j] == OFFSET:
                continue
            # n * m -> o
            pd.add_edge(i * m + j, n * m + cnt, 1, OFFSET - dist[i][j])
                

cnt_o = 0
for i in range(n):
    for j in range(m):
        if s[i][j] == "o":
            cnt_o += 1

pd = PrimalDual(n * m + cnt_o + 2)
start, goal = n * m + cnt_o, n * m + cnt_o + 1

# start -> n * m
for i in range(n):
    for j in range(m):
        pd.add_edge(start, i * m + j, 1, 0)

cnt = 0
for i in range(n):
    for j in range(m):
        if s[i][j] == "o":
            bfs(i, j, cnt)
            cnt += 1

print(OFFSET * cnt_o - pd.min_cost_flow(start, goal, cnt_o))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq


class PrimalDual:
    def __init__(self, n: int):
        """頂点数をnとする。"""
        self.INF = 10 ** 9 + 7
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, _from: int, to: int, capacity: int, cost: int):
        """辺を追加
        1. _fromからtoへ向かう容量capacity、単位コストcostの辺をグラフに追加する。
        2. toから_fromへ向かう容量0、単位コスト-costの辺をグラフに追加する。
        """
        forward = [to, capacity, cost, None]
        forward[3] = backward = [_from, 0, -cost, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)

    def min_cost_flow(self, s: int, t: int, f: int) -> int:
        """s-tパス上に流量fを流すときの最小費用流を求める。
        計算量: O(|F||E|log|V|)
        """
        res = 0
        potential = [0] * self.n
        prv_v = [0] * self.n
        prv_e = [None] * self.n
        while f > 0:
            # ポテンシャルを用いたダイクストラ法
            dist = [self.INF] * self.n
            dist[s] = 0
            q = [(0, s)]  # q = [(sからのコスト, 現在地)]
            while q:
                cost, _from = heapq.heappop(q)
                if dist[_from] < cost:
                    continue
                for edge in self.graph[_from]:
                    to, capacity, cost, _ = edge
                    p_diff = potential[_from] - potential[to]
                    if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
                        dist[to] = dist[_from] + cost + p_diff
                        prv_v[to] = _from
                        prv_e[to] = edge
                        heapq.heappush(q, (dist[to], to))

            if dist[t] == self.INF:
                return -1
            for i in range(self.n):
                if dist[i] != self.INF:
                    potential[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += potential[t] * d
            v = t
            while v != s:
                edge = prv_e[v]
                edge[1] -= d
                edge[3][1] += d
                v = prv_v[v]
        return res


n, m = map(int, input().split())
s = [input() for i in range(n)]
INF = 10 ** 18


def bfs(i, j, cnt):
    q = deque([(i, j)])
    dist = [[INF] * m for i in range(n)]
    dist[i][j] = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (0, 1)):
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < n and 0 <= nxt_j < m):
                continue
            if s[nxt_i][nxt_j] == "#":
                continue
            if dist[nxt_i][nxt_j] != INF:
                continue
            dist[nxt_i][nxt_j] = dist[i][j] + 1
            q.append((nxt_i, nxt_j))
    # o -> goal
    pd.add_edge(n * m + cnt, goal, 1, 0)
    for i in range(n):
        for j in range(m):
            if dist[i][j] == INF:
                continue
            # n * m -> o
            pd.add_edge(i * m + j, n * m + cnt, 1, -dist[i][j])
                

cnt_o = 0
for i in range(n):
    for j in range(m):
        if s[i][j] == "o":
            cnt_o += 1

pd = PrimalDual(n * m + cnt_o + 2)
start, goal = n * m + cnt_o, n * m + cnt_o + 1

# start -> n * m
for i in range(n):
    for j in range(m):
        pd.add_edge(start, i * m + j, 1, 0)

cnt = 0
for i in range(n):
    for j in range(m):
        if s[i][j] == "o":
            bfs(i, j, cnt)
            cnt += 1

print(-pd.min_cost_flow(start, goal, cnt_o))

Submission status: Time Limit Exceeded

Solution code:
# 最小費用流(minimum cost flow)
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost):
        # [to, cap, cost, rev]
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**9+7

        res = 0
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            if dist[t] == INF:
                return -1

            d = f; v = t
            while v != s:
                d = min(d, G[prevv[v]][preve[v]][1])
                v = prevv[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prevv[v]][preve[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prevv[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.minCostFlow(0,2501,os)
print(-ans)