#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__); template void Scan(T& t) { std::cin >> t; } templatevoid Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); } #define OUT(d) std::cout< c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector> c(m, std::vector(n));for(auto& r:c)for(auto& i:r)std::cin>>i; #define ALL(a) (a).begin(),(a).end() #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) for(int i=0;i=0;--i) #define FORLL(i, a, b) for(ll i=ll(a);i=ll(a);--i) #define REPLL(i, n) for(ll i=0;i=0;--i) #define PAIR std::pair #define IN(a, x, b) (a<=x && x(end-start).count();std::cerr<<"[Time:"< tmp(a);std::cout << #a << "\t:";for(int i=0; i(a.size()); ++i){std::cout << tmp.front() << "\n";tmp.pop();}std::cout << "\n";} //#define int ll using ll = long long; using ull = unsigned long long; constexpr int INFINT = 1 << 30; constexpr ll INFLL = 1LL << 60; constexpr double EPS = 0.0000000001; constexpr int MOD = 1000000007; class Dinic { private: struct Edge { int to, cap, rev; Edge(int t, int c, int r) :to(t), cap(c), rev(r){} }; int V; std::vector> graph; std::vector level, iter; public: Dinic(int v) : V(v) { graph.resize(v); level.resize(v, -1); iter.resize(v, 0); } // fromからtoへ向かう容量capの辺をグラフに追加する void addEdge(int from, int to, int cap) { graph[from].emplace_back(to, cap, graph[to].size()); graph[to].emplace_back(from, 0, graph[from].size() - 1); } // sからの最短距離をBFSで計算する void bfs(int s) { std::fill(level.begin(), level.end(), -1); std::queue queue; level[s] = 0; queue.push(s); while (!queue.empty()) { int v = queue.front(); queue.pop(); for (int i = 0; i < graph[v].size(); ++i) { Edge& e = graph[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; queue.push(e.to); } } } } // 増加パスをDFSで探す int dfs(int v, int t, int f) { if (v == t) return f; for (int& i = iter[v]; i < graph[v].size(); ++i) { Edge& e = graph[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, std::min(f, e.cap)); if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } // sからtへの最大流を求める int maxFlow(int s, int t) { int res = 0; while (true) { bfs(s); if (level[t] < 0) return res; std::fill(iter.begin(), iter.end(), 0); int f; while ((f = dfs(s, t, (1LL << 31) - 1)) > 0) { res += f; } } } }; signed main() { INIT; VAR(int, n, m); MAT(char, a, n, m); int s = n*m, t = n*m + 1; Dinic g(n*m + 2); int w = 0, b = 0; auto pos = [&](int i, int j) {return i*m + j; }; REP(i, n) REP(j, m) { switch (a[i][j]) { case 'w': { g.addEdge(s, pos(i, j), 1); ++w; if (i != 0 && a[i - 1][j] == 'b') g.addEdge(pos(i, j), pos(i - 1, j), 1); if (j != 0 && a[i][j - 1] == 'b') g.addEdge(pos(i, j), pos(i, j - 1), 1); if (i != n - 1 && a[i + 1][j] == 'b') g.addEdge(pos(i, j), pos(i + 1, j), 1); if (j != m - 1 && a[i][j + 1] == 'b') g.addEdge(pos(i, j), pos(i, j + 1), 1); break; } case 'b': { g.addEdge(pos(i, j), t, 1); ++b; break; } } } int maxFlow = g.maxFlow(s, t); int ans = 100 * maxFlow; w -= maxFlow; b -= maxFlow; ans += 10 * std::min(w, b); ans += std::max(w, b) - std::min(w, b); OUT(ans)BR; return 0; }