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 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 = [s]

            while que:
                c, v = divmod(heappop(que), N)
                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*N+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
MX = cnt
mcf = MinCostFlow(N*M+2)
s = N*M
t = N*M+1
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)

Submission status: Accepted

Solution code:

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

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

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

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

import heapq
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.es = [[] for _ in range(n)] #[[to,rev,cap,cost], ...]
        self.pos = []

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

    def get_edges(self):
        ret = []
        for fr,i in self.pos:
            to,rev,cap,cost = self.es[fr][i]
            flow = self.es[to][rev][2]
            cap += flow
            ret.append((fr, to, cap, flow, cost))
        return ret

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

    def slope(self, s, t, flow_limit=2**63):
        self.dual = [0] * self.n
        self.dist = [2**63] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n
        def _dual_ref():
            self.dist = [2**63] * self.n
            self.pv = [-1] * self.n
            self.pe = [-1] * self.n
            self.vis = [False] * self.n
            hq = [(0,s)]
            self.dist[s] = 0
            while hq:
                p = heapq.heappop(hq)
                v = p[1]
                if self.vis[v]: continue
                self.vis[v] = True
                if v==t: break
                for i,(to,rev,cap,cost) in enumerate(self.es[v]):
                    if self.vis[to] or not cap: continue
                    _cost = cost - self.dual[to] + self.dual[v]
                    if self.dist[to] - self.dist[v] > _cost:
                        self.dist[to] = self.dist[v] + _cost
                        self.pv[to] = v
                        self.pe[to] = i
                        heapq.heappush(hq, (self.dist[to],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
        flow, cost, prev_cost = 0, 0, -1
        ret = [(flow, cost)]
        while flow < flow_limit:
            if not _dual_ref(): break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.es[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                self.es[self.pv[v]][self.pe[v]][2] -= c
                self.es[v][self.es[self.pv[v]][self.pe[v]][1]][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                ret.pop()
            ret.append((flow, cost))
            prev_cost = cost
        return ret

mf = MinCostFlow(N*M+2)
src,dst = N*M, N*M+1
big = 10000
for i in range(N):
    for j in range(M):
        if S[i][j] == 'o':
            mf.add_edge(src, i*M+j, 1, i+j)
for i in range(N):
    for j in range(M):
        if S[i][j] == '#': continue
        if i+1 < N and S[i+1][j] != '#':
            mf.add_edge(i*M+j, (i+1)*M+j, big, 0)
        if j+1 < M and S[i][j+1] != '#':
            mf.add_edge(i*M+j, i*M+j+1, big, 0)
for i in range(N):
    for j in range(M):
        if S[i][j] == '#': continue
        mf.add_edge(i*M+j, dst, 1, big-(i+j))

flow,cost = mf.flow(src,dst)
ans = flow*big - cost
print(ans)