#!/usr/bin/env python3.8 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from collections import deque # %% class Dinic: def __init__(self, N, source, sink): self.N = N self.G = [[] for _ in range(N)] self.source = source self.sink = sink def add_edge(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加 def add_edge_undirected(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, cap, n1]) def bfs(self): level = [0] * self.N G = self.G source = self.source sink = self.sink q = deque([source]) level[source] = 1 pop = q.popleft append = q.append while q: v = pop() lv = level[v] + 1 for to, cap, rev in G[v]: if not cap: continue if level[to]: continue level[to] = lv if to == sink: self.level = level return append(to) self.level = level def dfs(self): INF = 10**18 G = self.G sink = self.sink prog = self.progress level = self.level ascend = False ff = 0 stack = [(self.source, INF)] while stack: if ff: # このまま更新だけして戻っていく v, f = stack.pop() p = prog[v] to, cap, rev = G[v][p] G[v][p][1] -= ff G[to][rev][1] += ff continue v, f = stack[-1] if v == sink: ff = f stack.pop() continue E = G[v] lv = level[v] if ascend: # 流せずに戻ってきた prog[v] += 1 find_flag = False for i in range(prog[v], len(E)): to, cap, rev = E[i] prog[v] = i if not cap: continue if level[to] <= lv: continue find_flag = True break if not find_flag: ascend = True stack.pop() continue ascend = False x = f if f < cap else cap stack.append((to, x)) return ff def max_flow(self): flow = 0 while True: self.bfs() if not self.level[self.sink]: return flow self.progress = [0] * self.N while True: f = self.dfs() if not f: break flow += f return flow # %% H, W = map(int, readline().split()) S = list(''.join(read().decode().split())) # %% source = H * W sink = H * W + 1 dinic = Dinic(N=H * W + 2, source=source, sink=sink) for h in range(H - 1): for w in range(W): i = W * h + w j = i + W if S[i] == 'b' and S[j] == 'w': dinic.add_edge(i, j, 1) elif S[i] == 'w' and S[j] == 'b': dinic.add_edge(j, i, 1) for h in range(H): for w in range(W - 1): i = W * h + w j = i + 1 if S[i] == 'b' and S[j] == 'w': dinic.add_edge(i, j, 1) elif S[i] == 'w' and S[j] == 'b': dinic.add_edge(j, i, 1) for i in range(H * W): if S[i] == 'b': dinic.add_edge(source, i, 1) elif S[i] == 'w': dinic.add_edge(i, sink, 1) # %% f = dinic.max_flow() # %% B = S.count('b') W = S.count('w') score = 100 * f B -= f W -= f x = min(B, W) score += 10 * x B -= x W -= x score += B + W print(score)