#include #include #include #include //#include #include #include #include #include #include //#include #include #include #include //#include #include //#include #include #include #include #include #include const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vll; typedef pair pii; // Dinic法:最小カット,最大フローで使う // 使い方: Dinic* dinic = new Dinic(V)で初期化(Vは頂点数) // dinic->add_edgeまたはdinic->add_edge_bothで点をつなげてdinic->max_flowで最大フローを求める #define NG -1 #define SZ(a) ((int)((a).size())) class Dinic { public: Dinic(int input_maxv) : maxv(input_maxv) { G.resize(input_maxv); level.resize(input_maxv); iter.resize(input_maxv); } void add_edge_both(int from, int to, int cap) { const int rev_from = SZ(G[from]); const int rev_to = SZ(G[to]); G[from].push_back(edge(to,cap,rev_to)); G[to].push_back(edge(from,cap,rev_from)); } void add_edge(int from, int to, int cap) { const int rev_from = SZ(G[from]); const int rev_to = SZ(G[to]); G[from].push_back(edge(to,cap,rev_to)); G[to].push_back(edge(from,0,rev_from)); } int max_flow(int s, int t) { int flow = 0; for(;;) { bfs(s); if(level[t]<0) break; fill(iter.begin(),iter.end(),0); int f; while( (f=dfs(s,t,DINIC_INF))>0) { flow += f; } } return flow; } vector get_nodes_in_group(int s) { vector ret(maxv); queue que; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); ret[v]=true; for(int i=0;i0 && !ret[e.to]) { que.push(e.to); } } } return ret; } void disp() { for (int v = 0; v < maxv; v++) { printf("%d:",v); for(int i=0;i0) { printf("->%d(%d),",G[v][i].to,G[v][i].init_cap); } } printf("\n"); } } private: void bfs(int s) { fill(level.begin(),level.end(),NG); queue que; level[s]=0; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for(int i=0;i0 && level[e.to]<0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v, int t, int f) { if(v==t) return f; for (int &i=iter[v];i0 && level[v]0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } static const int DINIC_INF = INT_MAX; struct edge { edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {} int to; int cap; int rev; int init_cap; }; int maxv; vector < vector > G; vector < int > level; vector < int > iter; }; string field[55]; int calc(int w, int b) { if (w > b) swap(w, b); return w*10 + b-w; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; for (int i = 0; i < N; i++) { cin >> field[i]; } int s = N*M, t = s+1, V = t+1; Dinic dinic(V); int W = 0, B = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (field[i][j] == '.') continue; if ((i+j)%2 == 0) { dinic.add_edge(s, i*M+j, 1); W++; } else { dinic.add_edge(i*M+j, t, 1); B++; } for (int k = 0; k < 4; k++) { int y = i+dy[k], x = j+dx[k]; if (y < 0 || y >= N || x < 0 || x >= M) continue; if (field[y][x] == 'b') { dinic.add_edge(i*M+j, y*M+x, 1); } } } int f = dinic.max_flow(s, t); int ans = f*100; W -= f, B -= f; ans += calc(W, B); cout << ans << endl; return 0; }