首先和 F1 一样，操作 \(2,3\) 依旧没有意义。
但是 F1 中至多使用一次操作 \(4\) 的结论到这里不成立了。
但是依旧可以发现一些有用的性质。
对于操作 \(4\)，会有 \(4\) 个格子的 \(a\) 发生改变，且这 \(4\) 个格子形如 \((x,y),(n,y),(x,m),(n,m)\)。记这样的操作为 \(op(x,y)\)。
结论 \(1\)：对于所有 \(op(x_i,y_i)\)，一定满足 \(x_i\) 互不相同且 \(y_i\) 互不相同，证明极其容易，反证说明若存在则只改变 \(4\) 个格子的状态不优于 \(4\) 次操作 \(1\)。
结论 \(2\)：我们只会操作 \(a_{x,y}=a_{x,m}=a_{n,y}=1\) 的格子。这是显然的，因为若上述三个格子至少有一个为 \(0\)，则不如花 \(2\) 的代价进行两次操作 \(1\) 而不是花 \(2+1=3\) 的代价进行一次操作 \(2\) 和至少一次操作 \(1\)（根据结论 \(1\) 易得因操作 \(2\) 由 \(0\) 变成 \(1\) 的格子必须用操作 \(1\) 而不是操作 \(2\) 弥补）。
第一个结论给予了我们很清晰的二分图匹配思路，第二个结论说明两部点之间连边的条件。因此根据上述结论建出左部点个数为 \(n-1\)，右部点个数为 \(m-1\) 的二分图，用 Dinic 跑一遍二分图匹配即可。时间复杂度 \(\mathcal O(n^{1.5}m)\)。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 505, M = 250005, inf = 0x3f3f3f3f;
int n, m;
int S, T;
char s[N];
int dep[N*2];
int head[N*2], now[N*2], ver[M*2], wei[M*2], nxt[M*2], cnt = 1;
int a[N][N], b[N][N];
int ans;
queue <int> q;
void add(int u, int v, int w) {
ver[++cnt] = v, wei[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
ver[++cnt] = u, wei[cnt] = 0, nxt[cnt] = head[v], head[v] = cnt;
}
bool bfs() {
memset(dep, -1, sizeof dep), dep[S] = 0;
while (q.size()) q.pop();
q.push(S), now[S] = head[S];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i], w = wei[i];
if (w && dep[v] == -1) {
dep[v] = dep[u] + 1, now[v] = head[v];
q.push(v);
if (v == T) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == T) return flow;
int res = flow;
for (int &i = now[u]; i; i = nxt[i]) {
int v = ver[i], w = wei[i];
if (w && dep[v] == dep[u] + 1) {
int k = dinic(v, min(res, w));
if (!k) dep[v] = -1;
wei[i] -= k, wei[i ^ 1] += k, res -= k;
}
if (!res) break;
}
return flow - res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
for (int j = 1; j <= m; ++j)
b[i][j] = (s[j] == 'B');
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = (b[i][j] ^ b[i + 1][j] ^ b[i][j + 1] ^ b[i + 1][j + 1]);
S = 0, T = n + m - 1;
for (int i = 1; i < n; ++i)
for (int j = 1; j < m; ++j)
if (a[i][j] && a[n][j] && a[i][m]) add(i, j + n - 1, 1);
for (int i = 1; i < n; ++i) add(S, i, 1);
for (int i = 1; i < m; ++i) add(i + n - 1, T, 1);
int flow, maxflow = 0;
while (bfs())
while (flow = dinic(S, inf)) maxflow += flow;
a[n][m] ^= (maxflow & 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += a[i][j];
printf("%d", ans - maxflow);
return 0;
}