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:
from collections import deque
import numpy as np

N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
moves = [(1, 0), (0, 1)]

starts = []
for i in range(N):
    for j in range(M):
        if S[i][j] == 'o':
            starts.append((i, j))

answer = 0
for start in starts:
    visited = np.full((N, M), -1)
    start_y, start_x = start

    q = deque()
    q.append((start_y, start_x))
    visited[start_y, start_x] = 0

    while q:
        y, x = q.popleft()

        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if moved_y < 0 or N-1 < moved_y or moved_x < 0 or M-1 < moved_x:
                continue
            if S[moved_y][moved_x] == '#' or S[moved_y][moved_x] == 'o':
                continue
            if visited[moved_y, moved_x] != -1:
                continue
            visited[moved_y, moved_x] = visited[y, x] + 1
            q.append((moved_y, moved_x))
    
    answer += np.max(visited)

print(answer)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_maxflow_code = """

from typing import NamedTuple, Optional, List


class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = e.rev
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = sum(e.cap for e in self._g[s])

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = e.rev
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited
"""

atcoder.maxflow = types.ModuleType('atcoder.maxflow')
exec(_atcoder_maxflow_code, atcoder.maxflow.__dict__)
MFGraph = atcoder.maxflow.MFGraph

# from atcoder.maxflow import MFGraph

n,m = map(int,input().split())
S = [input() for i in range(n)]
t = 100*(n+m) + 100
 

cap = 10**9


M = MFGraph(n*m*t + 2)
s = n*m*t
g = n*m*t+1
nm = n*m

for i in range(t-1):
    for j in range(n):
        for k in range(m):
            if S[j][k] != "#":
                if j+1 < n and S[j+1][k] != "#":
                    M.add_edge(i*nm+j*m+k, (i+1)*nm+(j+1)*m+k, cap)
                if k+1 < m and S[j][k+1] != "#":
                    M.add_edge(i*nm+j*m+k, (i+1)*nm+j*m+k+1, cap)

for i in range(1, t):
    for j in range(n):
        for k in range(m):
            if S[j][k] != "#":
                M.add_edge(i*nm+j*m+k, g, 1)
c=0
for j in range(n):
    for k in range(m):
        if S[j][k] == "o":
            c += 1
            M.add_edge(s, j*m+k, cap)

print(M.flow(s,g)-2*c)
# print(M.edges())

Submission status: Wrong Answer

Solution code:
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for i in range(h-1,-1,-1):
  for j in range(w):
    if board[i][j]=='o':
      checked=[[0]*w for _ in range(h)]
      checked[i][j]=1
      q=collections.deque()
      q.append((j,i,0))
      mx,my,md=-1,-1,0
      while len(q)!=0:
        x,y,d=q.popleft()
        if d>md and y>=my:
          mx,my,md=x,y,d
        for dx,dy in [[1,0],[0,1]]:
          if 0<=x+dx<w and 0<=y+dy<h and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==0:
            checked[y+dy][x+dx]=1
            q.append((x+dx,y+dy,d+1))
      if mx!=-1:
        board[i][j]='.'
        board[my][mx]='#'
        ans+=md
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

h,w=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for i in range(h-1,-1,-1):
  for j in range(w):
    if board[i][j]=='o':
      checked=[[0]*w for _ in range(h)]
      checked[i][j]=1
      q=collections.deque()
      q.append((j,i,0))
      mx,my,md=-1,-1,0
      while len(q)!=0:
        x,y,d=q.popleft()
        if d>md:
          mx,my,md=x,y,d
        for dx,dy in [[1,0],[0,1]]:
          if 0<=x+dx<w and 0<=y+dy<h and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==0:
            checked[y+dy][x+dx]=1
            q.append((x+dx,y+dy,d+1))
      if mx!=-1:
        board[i][j]='.'
        board[my][mx]='#'
        ans+=md
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  if S[now[0]][now[1]]=='#':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    dx,dy = (-1,0),(0,-1)
    for i in range(2):
      new = (now[0]+dx[i], now[1]+dy[i])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':continue
      seen[new[0]][new[1]] = 1
      todo.append(new)
      d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

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

#print(bfs((8,6)))

ss = set()
for i in range(H):
  for j in range(W):
    if S[i][j]=='o':
      ss.add((i,j))
#print(ss)
ans = 0
for i in range(H-1,-1,-1):
  for j in range(W-1,-1,-1):
    if S[i][j] == '#': continue
    if S[i][j] == 'o' and (i,j) in ss:
      ss.remove((i,j))
      continue
    d = bfs((i,j))
    MAX,argmax=0,-1
    for sx,sy in ss:
      if d[sx][sy] > MAX:
        MAX = d[sx][sy]
        argmax = (sx,sy)
    if MAX > 0:
      ss.remove(argmax)
      ans += MAX
      
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


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


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()
                update = False
                if i + 1 < N and grid[i + 1][j] != "#":
                    update = True
                    dist[i+1][j] = dist[i][j] + 1
                    node.append((i + 1, j))
                if j + 1 < M and grid[i][j + 1] != "#":
                    update = True
                    dist[i][j+1] = dist[i][j] + 1
                    node.append((i, j + 1))
                if not update:
                    g.add_edge(v, i*M+j, 1, inf - dist[i][j])

g.add_edge(source, sink, piece, inf)

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

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=[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,X)
g.flow(s,t)
print(sum([e[3] for e in g.edges() if e[0]!=s and e[1]!=t]))

Submission status: Wrong Answer

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


from collections import deque

ans = 0
for i in range(N+M-2,-1,-1):
    for k in range(N):
        h,w = k,i-k
        if w<0 or M<=w:
            continue

        if S[h][w]=="o":
            deq = deque([h*64+w])
            S[h][w] = "."
            pre_h,pre_w = h,w
            lasth,lastw = h,w
            while deq:
                v = deq.popleft()
                h,w = v>>6,v&63
                if h!=N-1 and S[h+1][w]==".":
                    lasth,lastw = h+1,w
                    deq.append((h+1)*64+w)
                if w!=M-1 and S[h][w+1]==".":
                    lasth,lastw = h,w+1
                    deq.append((h)*64+w+1)

            ans += lasth + lastw - pre_h - pre_w
            S[lasth][lastw] = "o"

print(ans)

Submission status: Wrong Answer

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)

    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, INF - 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 = INF * 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)