#include using namespace std; using ll = long long; using VI = vector; using VL = vector; using PII = std::pair; using PLL = std::pair; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define allpt(v) (v).begin(), (v).end() #define allpt_r(v) (v).rbegin(), (v).rend() const int mod = 1e9 + 7; const string wsp = " "; const string tb = "\t"; const string rt = "\n"; template void show1dvec(vector v) { if (v.size() == 0) return; int n = v.size() - 1; rep(i, n) cout << v[i] << wsp; cout << v[n] << rt; return; } template void show2dvec(vector> v) { int n = v.size(); rep(i, n) show1dvec(v[i]); } const int INTMAX = 2 * 1e9 + 10; const int NMAX = 3 * 1e3; bool check[NMAX]; template int dfs(int s, int t, T f, vector> edge[], vector &used) { int d = 0; check[s] = true; if (s == t) { used.push_back(t); return f; } for (auto next : edge[s]) { if (!check[next.first] && next.second > 0) d = dfs(next.first, t, min(next.second, f), edge, used); if (d > 0) { used.push_back(s); return d; } // DFSが終点まで行くと正の値dが帰ってくるので、辺の容量の調整をして終了 } return 0; //そうでなければ何もしない } int main() { #ifdef DEBUG cout << "DEBUG MODE" << endl; ifstream in("input.txt"); //for debug cin.rdbuf(in.rdbuf()); //for debug #endif int n, m, h, w, s, t, c, a, b, f, adjust_pair, black, white, distant_pair, total_score; cin >> h >> w; n = h * w + 2; f = 1, adjust_pair = black = white = distant_pair = total_score = 0; vector field(h); vector> edge[n]; vector used; rep(i, h) { cin >> field[i]; rep(j, w) { if (field[i][j] == 'w') { white++; edge[0].push_back(make_pair(w * i + j + 1, 1)); edge[w * i + j + 1].push_back(make_pair(0, 0)); } else if (field[i][j] == 'b') { black++; edge[n - 1].push_back(make_pair(w * i + j + 1, 0)); edge[w * i + j + 1].push_back(make_pair(n - 1, 1)); } } } rep(i, h) rep(j, w - 1) { if (field[i][j] == 'w' && field[i][j + 1] == 'b') { edge[w * i + j + 1].push_back(make_pair(w * i + j + 2, 1)); edge[w * i + j + 2].push_back(make_pair(w * i + j + 1, 0)); } else if (field[i][j] == 'b' && field[i][j + 1] == 'w') { edge[w * i + j + 1].push_back(make_pair(w * i + j + 2, 0)); edge[w * i + j + 2].push_back(make_pair(w * i + j + 1, 1)); } } rep(i, h - 1) rep(j, w) { if (field[i][j] == 'w' && field[i + 1][j] == 'b') { edge[w * i + j + 1].push_back(make_pair(w * i + w + j + 1, 1)); edge[w * i + w + j + 1].push_back(make_pair(w * i + j + 1, 0)); } else if (field[i][j] == 'b' && field[i + 1][j] == 'w') { edge[w * i + j + 1].push_back(make_pair(w * i + w + j + 1, 0)); edge[w * i + w + j + 1].push_back(make_pair(w * i + j + 1, 1)); } } while (f > 0) { fill(check, check + n, false); f = dfs(0, n - 1, INTMAX, edge, used); a = -1, b = -1; for (auto i : used) { a = b; b = i; if (a >= 0 && b >= 0) { for (auto &j : edge[a]) { if (j.first == b) { j.second += f; break; } } for (auto &j : edge[b]) { if (j.first == a) { j.second -= f; break; } } } } adjust_pair += f; used.clear(); } white -= adjust_pair, black -= adjust_pair; distant_pair = min(white, black); white -= distant_pair, black -= distant_pair; total_score = 100 * adjust_pair + 10 * distant_pair + white + black; cout << total_score << endl; return 0; }