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:
import heapq
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  def __init__ (s, n):
    s._n = n
    s.g = [[] for _ in range(n)]
    s.pos = []

  def add_edge(s, frm, to, cap, cost):
    m = len(s.pos)
    s.pos.append([frm, len(s.g[frm])])
    s.g[frm].append(s._edge(to, len(s.g[to]), cap, cost))
    s.g[to].append(s._edge(frm, len(s.g[frm]) - 1, 0, -cost))
    return m

  class edge:
    __slots__ = "frm", "to", "cap", "flow", "cost"
    def __init__(s, frm, to, cap, flow, cost):
      s.frm, s.to = frm, to
      s.cap, s.flow, s.cost = cap, flow, cost

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

  def edges(s):
    for i in range(len(s.pos)):
      yield s.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):
    #priority_queueの代わり
    push = heapq.heappush
    pop = heapq.heappop

    dist = [NUMERIC_LIMITS] * self._n
    self.pv = [-1] * self._n
    self.pe = [-1] * self._n
    vis = [False] * self._n
    que = []
    dist[s] = 0
    push(que, (0, s))
    while que:
      k, v = pop(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
          push(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__(s, to, rev, cap, cost):
      s.to, s.rev = to, rev
      s.cap, s.cost = cap, cost


N, M = list(map(int, input().split()))
s = [list(input()) for _ in range(N)]

flow = mcf_graph(N * M + 2)
S = N * M
T = N * M + 1
ans = 0
cnt = 0
for n in range(N):
  for m in range(M):
    if s[n][m] == "#": continue
    x = n * M + m
    if m + 1 < M:
      if s[n][m + 1] != "#":
        y = n * M + m + 1
        flow.add_edge(x, y, N * M, 0)
    if n + 1 < N:
      if s[n + 1][m] != "#":
        y = (n + 1) * M + m
        flow.add_edge(x, y, N * M, 0)
    if s[n][m] == "o":
      flow.add_edge(S, x, 1, 0)
      ans += n + m
      cnt += 1
    flow.add_edge(x, T, 1, N + M -(n + m))

f = flow.flow(S, T, cnt)[1]

print((N + M) * cnt - f - ans)

Submission status: Accepted

Solution code:
import networkx as nx

n, m = map(int, input().split())
s = [input() for _ in range(n)]
g = nx.DiGraph()
S, T = n*m, n*m+1
pot, cnt = 0, 0
for i in range(n):
	for j in range(m):
		if s[i][j] == "#":
			continue
		g.add_edge(i*m+j, T, capacity=1, weight=n+m-i-j)
		if s[i][j] == "o":
			g.add_edge(S, i*m+j, capacity=1, weight=0)
			pot += n+m-i-j
			cnt += 1
		if i < n-1 and s[i+1][j] != "#":
			g.add_edge(i*m+j, (i+1)*m+j, capacity=100, weight=0)
		if j < m-1 and s[i][j+1] != "#":
			g.add_edge(i*m+j, i*m+j+1, capacity=100, weight=0)
g.add_node(S, demand=-cnt)
g.add_node(T, demand=cnt)
ans, _ = nx.algorithms.flow.network_simplex(g)
print(pot - ans)

Submission status: Accepted

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 < M and X[i][j+1]:
            b = a + 1
            G.add_edge(a, b, capacity = N * M, weight = -1)

print(-min_cost_flow_cost(G))

Submission status: Accepted

Solution code:
import heapq as hp
class MinimumCostFlow():
    def __init__(self, N, INF=10**18):
        self.graph = [{} for _ in range(N)]
        self.N = N
        self.INF = INF
    
    def add_edge(self, u, v, cap, cost, undirected=False):
        # u -> v (maxflow, cost)
        if cap == 0: return
        if undirected:
            self.graph[u][v] = [cap, cost]
            self.graph[v][u] = [cap, -cost]
        elif v in self.graph[u]:
            self.graph[u][v] = [cap, cost]
        else:
            self.graph[u][v] = [cap, cost]
            self.graph[v][u] = [0, -cost]       
    
    def dijkstra(self, start):
        self.dist = [self.INF]*self.N # nearest distance
        self.dist[start] = 0
        self.que = [(0, start)]
        while self.que:
            d, v = hp.heappop(self.que)
            if self.dist[v] < d: continue
            for nv, (ncap, ncost) in self.graph[v].items():
                if ncap > 0 and self.dist[nv] > self.dist[v] + ncost + self.H[v] - self.H[nv]:
                    self.dist[nv] = self.dist[v] + ncost + self.H[v] - self.H[nv]
                    self.prevv[nv] = v
                    hp.heappush(self.que, (self.dist[nv], nv))
                
    
    def min_cost_flow(self, start, finish, flow):
        self.res = 0
        self.prevv = [-1]*self.N
        self.H = [0]*self.N # potential
        while flow > 0:
            self.dijkstra(start)
            if self.dist[finish] == self.INF: return -1 # cant run flow anymore
            for i in range(self.N):
                self.H[i] += self.dist[i]
            
            d = flow
            v = finish
            while v != start:
                d = min(d, self.graph[self.prevv[v]][v][0])
                v = self.prevv[v]
            flow -= d
            self.res += d*self.H[finish]

            v = finish
            while v != start:
                self.graph[self.prevv[v]][v][0] -= d
                self.graph[v][self.prevv[v]][0] += d
                v = self.prevv[v]
        return self.res
    

INF = 10**5
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = N*M
State = [list(input().rstrip()) for _ in range(N)]

FL = MinimumCostFlow(2*L+2)
c = 0
for n in range(N):
    for m in range(M):
        if State[n][m] == "o":
            FL.add_edge(2*L, m*N+n, 1, INF)
            c += 1
            cango = {(n-1, m)}
            for an in range(n, N):
                for am in range(m, M):
                    if ((an-1, am) in cango or (an, am-1) in cango) and State[an][am] != "#":
                        cango.add((an, am))
                        dist = an - n + am - m
                        FL.add_edge(m*N+n, L+am*N+an, 1, INF-dist)
        if State[n][m] != "#":
            FL.add_edge(m*N+n+L, 2*L+1, 1, INF)

ans = 3*c*INF - FL.min_cost_flow(2*L, 2*L+1, c)
print(ans)

Submission status: Accepted

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

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf
    
    #二部グラフのマッチング復元の時はsinkとつながってる辺のうち容量が０でなくsink出ない辺の先がマッチング対象

from heapq import heappop as hpp, heappush as hp
class MinCostFlowwithDijkstra:
    INF = 1<<60
    
    def __init__(self, N):
        self.N = N
        self.Edge = [[] for _ in range(N)]
    
    def add_edge(self, st, en, cap, cost):
        self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
        self.Edge[en].append([st, 0, -cost, len(self.Edge[st])-1])
    
    def get_mf(self, so, si, fl):
        N = self.N
        INF = self.INF
        res = 0
        Pot = [0]*N
        geta = N
        
        
        prv = [None]*N
        prenum = [None]*N
        while fl:
            dist = [INF]*N
            dist[so] = 0
            Q = [so]
            
            while Q:
                cost, vn = divmod(hpp(Q), geta)
                if dist[vn] < cost:
                    continue
                
                for enum in range(len(self.Edge[vn])):
                    vf, cap, cost, _ = self.Edge[vn][enum]
                    cc = dist[vn] + cost - Pot[vn] + Pot[vf]
                    if cap > 0 and dist[vf] > cc:
                        dist[vf] = cc
                        prv[vf] = vn
                        prenum[vf] = enum
                        hp(Q, cc*geta + vf)
            
            if dist[si] == INF:
                return -1
            
            for i in range(N):
                Pot[i] -= dist[i]
            
            cfl = fl
            vf = si
            while vf != so:
                cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
                vf = prv[vf]
            
            fl -= cfl
            res -= cfl*Pot[si]
            vf = si
            while vf != so:
                e = self.Edge[prv[vf]][prenum[vf]]
                e[1] -= cfl
                self.Edge[vf][e[3]][1] += cfl
                vf = prv[vf]
        return res

N, M = map(int, readline().split())

G = []

wall = ord('#')
st = ord('o')
S = []
css = 0
for i in range(N):
    k = list(map(ord, readline().strip()))
    res = []
    for j in range(M):
        if k[j] == st:
            S.append((i, j))
            css += 1
        if k[j] == wall:
            res.append(1)
        else:
            res.append(0)
    G.append(res)

geta1 = N*M
geta2 = M
so = 2*N*M
si = so + 1
FF = MinCostFlowwithDijkstra(2*N*M+2)

INF = 10**9+7
for i, j in S:
    stack = [(i, j)]
    used = set((i, j))
    FF.add_edge(so, i*geta2+j, 1, 0)
    FF.add_edge(i*geta2+j, geta1+i*geta2+j, 1, INF)
    while stack:
        vi, vj = stack.pop()
        for di, dj in ((1, 0), (0, 1)):
            fi, fj = vi+di, vj+dj
            if 0 <= fi < N and 0 <= fj < M and not G[fi][fj]:
                if (fi, fj) not in used:
                    used.add((fi, fj))
                    stack.append((fi, fj))
                    cost = INF - (fi-i) - (fj-j)
                    FF.add_edge(i*geta2+j, geta1+fi*geta2+fj, 1, cost)

for i in range(N):
    for j in range(M):
        if G[i][j]:
            continue
        FF.add_edge(geta1+i*geta2+j, si, 1, 0)

print(css*INF-FF.get_mf(so, si, css))

Submission status: Accepted

Solution code:


code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.utility cimport pair
from libcpp.string cimport string
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "<atcoder/mincostflow>" namespace "atcoder":
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int fr, 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'
            int to
            Cap cap
            Cap flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()

cdef class McfGraph:
    cdef mcf_graph[int, ll] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new mcf_graph[int, ll](n)
    cpdef int add_edge(self, int fr, int to, int cap, ll cost):
        return self._thisptr.add_edge(fr, to, cap, cost)
    cpdef pair[int, ll] flow(self, int s, int t):
        return self._thisptr.flow(s, t)
    cpdef pair[int, ll] flow_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.flow(s, t, flow_limit)
    cpdef vector[pair[int, ll]] slope(self, int s, int t):
        return self._thisptr.slope(s, t)
    cpdef vector[pair[int, ll]] slope_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.slope(s, t, flow_limit)

    cpdef pair[vector[int], ll] get_edge(self, int i):
        cdef mcf_graph[int, ll].edge *e = new mcf_graph[int, ll].edge(self._thisptr.get_edge(i))
        cdef pair[vector[int], ll] *ret_e = new pair[vector[int], ll]()
        ret_e.first.push_back(e.frm)
        ret_e.first.push_back(e.to)
        ret_e.first.push_back(e.cap)
        ret_e.first.push_back(e.flow)
        ret_e.second = e.cost
        return ret_e[0]

    cpdef vector[pair[vector[int], ll]] edges(self):
        cdef vector[mcf_graph[int, ll].edge] es = self._thisptr.edges()
        cdef vector[pair[vector[int], ll]] *ret_es = new vector[pair[vector[int], ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).first.push_back(es.at(i).frm)
            ret_es.at(i).first.push_back(es.at(i).to)
            ret_es.at(i).first.push_back(es.at(i).cap)
            ret_es.at(i).first.push_back(es.at(i).flow)
            ret_es.at(i).second = es.at(i).cost
        return ret_es[0]
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import McfGraph, ReadInt, Read

N, M = ReadInt(2)
S = [r.decode() for r in Read(N)]

mg = McfGraph(N*M+2)
s = N*M
t = N*M+1
BIG = 1000

def I(i,j):
    return i*M+j

initial = 0

for i in range(N):
    for j in range(M):
        x = I(i,j)
        if S[i][j]=="o":
            mg.add_edge(s,x,1,0)
            initial+=BIG-i-j
        if S[i][j]!="#":
            mg.add_edge(x,t,1,BIG-i-j)
        if i<N-1:
            if S[i][j]!="#" and S[i+1][j]!="#":
                mg.add_edge(x,I(i+1,j),BIG,0)
        if j<M-1:
            if S[i][j]!="#" and S[i][j+1]!="#":
                mg.add_edge(x,I(i,j+1),BIG,0)

n, score = mg.flow(s,t)
print(initial-score)

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 ** 10

    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 + s_size + 2)
    s = nm + s_size
    t = s + 1

    stack = np.zeros(10 ** 7, np.int64)
    SENTINEL = INF - 1

    for i in range(s_size):
        mincostflow_add_link(ins, s, nm + i, 1, 0)

        stack[0] = starts[i]
        stack[1] = 0
        sl = 0
        sr = 2
        stacked = np.zeros(nm, np.int8)
        stacked[starts[i]] = 1
        while sl < sr:
            v = stack[sl]
            c = stack[sl + 1]
            sl += 2

            mincostflow_add_link(ins, nm + i, v, 1, SENTINEL - c)

            if stacked[v + 1] == 0 and field[v + 1] != 2:
                stack[sr] = v + 1
                stack[sr + 1] = c + 1
                stacked[v + 1] = 1
                sr += 2
            if stacked[v + m2] == 0 and field[v + m2] != 2:
                stack[sr] = v + m2
                stack[sr + 1] = c + 1
                stacked[v + m2] = 1
                sr += 2

    for i in range(nm):
        if field[i] != 2:
            mincostflow_add_link(ins, i, t, 1, 0)

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

    ans = SENTINEL * 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 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] # s ==  (0 << 32) + 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


BIG = 10 ** 9


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

graph = mcf_graph_int_cost(2 * N * M + 2)

s = 2 * N * M
t = 2 * N * M + 1

for i in range(N * M):
    graph.add_edge(s, i, 1, 0)
    graph.add_edge(i + N * M, t, 1, 0)

ocount = 0
for oi in range(N):
    for oj in range(M):
        if board[oi][oj] == 'o':
            ocount += 1
            checked = [[False] * M for _ in range(N)]
            checked[oi][oj] = True
            st = [M * oi + oj]
            while st:
                p = st.pop()
                i, j = divmod(p, M)
                graph.add_edge(oi * M + oj, p + N * M, 1, BIG - (j - oj) - (i - oi))
                if i + 1 < N and board[i + 1][j] != '#' and not checked[i + 1][j]:
                    checked[i + 1][j] = True
                    st.append((i + 1) * M + j)
                if j + 1 < M and board[i][j + 1] != '#' and not checked[i][j + 1]:
                    checked[i][j + 1] = True
                    st.append(i * M + j + 1)

tmp = graph.flow(s, t, N * M * N * M)
print(BIG * ocount - tmp[1])

Submission status: Accepted

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*logV) """

    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):
        from heapq import heappush, heappop

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

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

        while f:
            dist = [INF] * N
            dist[s] = 0
            que = [(0, s)]

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

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

            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 * H[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
offset = 3000

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, offset)
        if grid[i][j] in ['o', '.']:
            mcf.add_edge(i*M+j, t, 1, offset)
            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 = offset*MX*2 - mcf.flow(s, t, MX)
print(ans)