#include using namespace std; struct Hungarian { const int INF = 1e9; int n, p, q; vector> mat; vector fx, fy, x, y; Hungarian(const vector>& mat) : n(mat.size()), mat(mat), fx(mat.size(), INF), fy(mat.size()), x(mat.size(), -1), y(mat.size(), -1) {} int run() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { fx[i] = max(fx[i], mat[i][j]); } } for (int i = 0; i < n;) { vector t(n, -1), s(n + 1, i); for (p = q = 0; p <= q && x[i] < 0; p++) { for (int k = s[p], j = 0; j < n && x[i] < 0; j++) { if (fx[k] + fy[j] == mat[k][j] && t[j] < 0) { s[++q] = y[j]; t[j] = k; if (s[q] < 0) { for (p = j; p >= 0; j = p) { y[j] = k = t[j]; p = x[k]; x[k] = j; } } } } } if (x[i] < 0) { int d = INF; for (int k = 0; k <= q; k++) { for (int j = 0; j < n; j++) { if (t[j] < 0) { d = min(d, fx[s[k]] + fy[j] - mat[s[k]][j]); } } } for (int j = 0; j < n; j++) { fy[j] += (t[j] < 0 ? 0 : d); } for (int k = 0; k <= q; k++) { fx[s[k]] -= d; } } else { i++; } } int ret = 0; for (int i = 0; i < n; i++) { ret += mat[i][x[i]]; } return ret; } int match_y(int k) { return x[k]; } int match_x(int k) { return y[k]; } }; int main() { int n, m; cin >> n >> m; vector> board(n, vector(m, -1)); int w = 0, b = 0; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) { if (s[j] == 'w') board[i][j] = w++; else if (s[j] == 'b') board[i][j] = 10000 + b++; } } int k = max(w, b); vector> mat(k, vector(k)); auto is_next = [](int i, int j, int ii, int jj) { return abs(i - ii) + abs(j - jj) == 1; }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int ii = 0; ii < n; ii++) { for (int jj = 0; jj < m; jj++) { if (0 <= board[i][j] && board[i][j] < 10000 && 10000 <= board[ii][jj]) { if (is_next(i, j, ii, jj)) { mat[board[i][j]][board[ii][jj] - 10000] = 100; } else { mat[board[i][j]][board[ii][jj] - 10000] = 10; } } } } } } Hungarian h(mat); cout << h.run() + abs(w - b) << endl; }