#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define FOR(i,a,b) for(int i= (a); i<((int)b); ++i) #define RFOR(i,a) for(int i=(a); i >= 0; --i) #define FOE(i,a) for(auto i : a) #define SZ(x) ((int)(x).size()) #define ALL(c) (c).begin(), (c).end() #define RALL(c) (c).rbegin(), (c).rend() #define AND && #define OR || #define NOT ! #define SUM(x) std::accumulate(ALL(x), 0LL) #define EPS 1e-14 template inline void DUMP(T x) { std::cerr << x << std::endl; } template inline void DUMP_V(std::vector v) { for (unsigned int i = 0; i < v.size(); ++i) { std::cerr << v[i] << ((i == v.size() - 1) ? "n" : " "); } } template inline void DUMP_V2(std::vector> v) { for (unsigned int i = 0; i < v.size(); ++i) { for (unsigned int j = 0; j < v[i].size(); ++j) { std::cerr << v[i][j] << " "; } std::cerr << std::endl; } } using namespace std; class FordFulkerson { private: struct Edge { int to; int capacity; int rev; }; // 辺(行き先、容量、逆辺のidx(Graph[to][rev]でアクセス)) map> Graph; // グラフ(ノード番号: {辺1, 辺2, ...}) // fromからtoまでの増加パスをDFSで探す int dfs(int from, int sink, int flow, set &used) { if (from == sink) return flow; used.insert(from); for (Edge &e : Graph[from]) { if (used.find(e.to) == used.end() && e.capacity > 0) { int d = dfs(e.to, sink, min(flow, e.capacity), used); // 流せる if (d > 0) { e.capacity -= d; Graph[e.to][e.rev].capacity += d; return d; } } } // fromからtoへのパスがみつからない return 0; } public: // グラフに辺を追加 void addEdge(int from, int to, int capacity) { Graph[from].push_back({ to, capacity, (int)Graph[to].size() }); Graph[to].push_back({ from, 0, (int)Graph[from].size() - 1 }); } // sourceからsinkへの最大流を求める // O(F|E|) Fは最大の流量 int maxFlow(int source, int sink) { int flow = 0; while (true) { set used; int f = dfs(source, sink, INT_MAX, used); if (f == 0) { break; }; flow += f; } return flow; } }; // 4近傍(右, 下, 左, 上) vector dy = { 0, -1, 0, 1 }; vector dx = { 1, 0, -1, 0 }; bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; } int main(int argc, char *argv[]) { FordFulkerson ff; int n, m; string s; vector v; cin >> n >> m; FOR(i, 0, n) { cin >> s; v.push_back(s); } int source = n * m + 1; int sink = n * m + 2; int w = 0; int b = 0; FOR(y, 0, n) { FOR(x, 0, m) { int node = y * m + x; if (v[y][x] == 'w') { w++; ff.addEdge(source, node, 1); for (int i = 0; i < dy.size(); i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (inside(ny, nx, n, m)) { if (v[ny][nx] == 'b') { int black = ny * m + nx; ff.addEdge(node, black, 1); } } } } else if (v[y][x] == 'b') { b++; ff.addEdge(node, sink, 1); } } } int ans = 0; int p = ff.maxFlow(source, sink); cout << p << endl; ans += p * 100; w -= p; b -= p; int t = min(w, b); ans += t * 10; ans += max(w, b) - t; cout << ans << endl; return 0; }