CF1592F1 Alice and Recoloring 1 题解
题意：
本题与 CF1592F2 的差异在于花费不同。
给定一个 $n$ 行 $m$ 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
- 使用一块钱，选定一个包含 $(1,1)$ 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
- 使用两块钱，选定一个包含 $(n,1)$ 的子矩阵，把矩阵中的元素全部反转。
- 使用四块钱，选定一个包含 $(1,m)$ 的子矩阵，把矩阵中的元素全部反转。
- 使用三块钱，选定一个包含 $(n,m)$ 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
输入格式：
第一行两个正整数 $n$ 和 $m (1 \le n,m\le 500)$ ，意义如上文所述。
接下来 $n$ 行，每行 $m$ 个字符 W 或 B 。意义如上文所述。
输出格式：
一行一个整数，表示把初始矩阵变为目标矩阵所需的最少钱数。
先做了 F2 再做的 F1，因此本题解可能比较简陋，F2 的题解链接
首先注意到 $(n,1)$ 的操作和 $(1,m)$ 的操作都是没意义的，都可以用 $(1,1)$ 的操作替代。
于是问题转化为，只有两种操作 $(1,1)$ 和 $(n,m)$ ，价格分别是 $1$ 和 $3$ 元。
对 $a_{i,j}$ 做一遍异或后缀和（ W 为 $1$ ），也就是 $a_{i,j} \gets a_{i, j} \oplus a_{i, j+1} \oplus a_{i+1, j} \oplus a_{i+1, j+1}$ 。
那么操作一就变成了取反 $a_{i,j}$，操作二变成了取反 $a_{i,j},\,a_{i,m},\,a_{n,j},\,a_{n,m}$ 。（要是做前缀和就是反过来）
然后因为先做了 F2 所以这里即很简单了，这里操作二改 $4$ 个点只需要 $3$ 块，而且只需要改一次
那么我们直接贪心把这些能改的点全改了即可，最后剩下的用 $1$ 取改。
时间复杂度 $\mathcal{O}(nm)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(555))
char s[N][N]; int res, a[N][N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n, m; cin >> n >> m;
rep(i, 1, n) cin >> (s[i] + 1);
rep(i, 1, n) rep(j, 1, m) {
res += (a[i][j] = (s[i][j] == 'B') ^ (s[i][j + 1] == 'B')
^ (s[i + 1][j] == 'B') ^ (s[i + 1][j + 1] == 'B'));
}
for(int i = 1, ok = 0; i < n && !ok; i++)
for(int j = 1; j < m && !ok; j++)
if(a[i][j] && a[i][m] && a[n][j] && a[n][m]) { ok = true, --res; }
cout << res << '\n';
return 0;
}
