#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 REP(i, n) for (int (i) = 0; (i) < (n); (i)++) #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++) #define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--) #define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--) #define PI acos(-1.0) #define DEBUG(C) cerr << C << endl; #define VI vector #define VII vector #define VL vector #define VLL vector #define VD vector #define VDD vector #define PII pair #define PDD pair #define PLL pair #define VPII vector #define ALL(a) (a).begin(), (a).end() #define SORT(a) sort(ALL(a)) #define REVERSE(a) reverse(ALL(a)) #define MP make_pair #define EB emplace_back #define FORE(a, b) for (auto &&a : b) #define FIND(s, n) (s.find(n) != s.end()) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9; const int MOD = INF + 7; const LL LLINF = 1e18; class FordFulkerson { struct edge { int to, rev; //行き先,逆辺(のid) long long cap; //容量 edge(int _to, int _rev, long long _cap) { this->to = _to; this->rev = _rev; this->cap = _cap; } }; private: vector> G; vector used; long long dfs(int v, int t, long long f) { if (v == t) return f; used[v] = true; FORE(el, G[v]) { if (used[el.to] || el.cap <= 0) { continue; } long long d = dfs(el.to, t, min(f, el.cap)); if (d > 0) { el.cap -= d; G[el.to][el.rev].cap += d; return d; } } return 0; } public: FordFulkerson() {} FordFulkerson(int n) { G.resize(n); used.resize(n, false); } void add_edge(int from, int to, long long cap) { G[from].emplace_back(edge(to, G[to].size(), cap)); G[to].emplace_back(edge(from, G[from].size() - 1, 0)); } long long max_flow(int s, int t) { if (s == t) return -1; long long flow = 0; while (1) { fill(begin(used), end(used), false); long long f = dfs(s, t, LLINF); if (f == 0) return flow; flow += f; } } }; int dx[] = {-1, 0, 0, 1}; int dy[] = {0, -1, 1, 0}; int N, M; bool inside(int ii, int jj) { return 0 <= ii && ii < N && 0 <= jj && jj < M; } int main(void) { cin >> N >> M; FordFulkerson mf(N * M + 10); int s = N * M, t = s + 1; vector S(N); REP(i, N) cin >> S[i]; int white = 0, black = 0; REP(i, N)REP(j, M) { if (S[i][j] == 'w') { white++; mf.add_edge(s, i * M + j, 1); } if (S[i][j] == 'b') { black++; mf.add_edge(i * M + j, t, 1); continue; } REP(k, 4) { int ni = i + dx[k]; int nj = j + dy[k]; if (!inside(ni, nj)) continue; if (S[ni][nj] == '.') continue; mf.add_edge(i * M + j, ni * M + nj, 1); } } LL flow = mf.max_flow(s, t); LL ans = flow * 100; white -= flow; black -= flow; ans += min(white, black) * 10; ans += max(white, black) - min(white, black); cout << ans << endl; }