题目描述

题目传送门

思路

没想到对矩阵的转化qwq

不妨假设 W11B00

显然操作 2、3 都可以由两次操作 1 容斥得到,而且花费更优。可以不考虑。

于是我们只需要考虑操作 1、4 的贡献。

矩阵的全部元素翻转相当于子矩阵异或 11。处理矩阵很麻烦,有没有办法将矩阵信息拍平到几个点上呢?

可以考虑构造 ai,j=ci,jci+1,jci,j+1ci+1,j+1a_{i,j} = c_{i,j} \oplus c_{i+1,j} \oplus c_{i,j + 1} \oplus c_{i + 1,j + 1}

这样有什么好处呢?

可以发现操作一变成了 ax,ya_{x,y} 异或 11,操作四变成了 ax1,y1,ax1,m,an,y1,an,ma_{x-1,y-1},a_{x-1,m},a_{n,y-1},a_{n,m} 异或 11

操作四只能选定四个为 11 的点进行一次,不然会带来负影响。时间复杂度 Θ(nm)\mathcal{\Theta(nm)}

代码

#include <bits/stdc++.h>
using namespace std;
int w(char c) { return (c == 'B'); }

char c[510][510];
int n, m, a[510][510], Ans;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> (c[i] + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) 
			Ans += (a[i][j] = (w(c[i + 1][j + 1]) ^ w(c[i + 1][j]) ^ w(c[i][j + 1]) ^ w(c[i][j])));
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++)
			if (a[i - 1][j - 1] && a[i - 1][m] && a[n][j - 1] && a[n][m]) {
				Ans--;
				goto End;
			}
	End:;
	cout << Ans << endl;
	return 0;
}