题目
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
- 使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
- 使用两块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
- 使用三块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
思路
将初始矩阵变为目标矩阵等价于将目标矩阵变为初始矩阵(元素全为W).
我们用数组\(map_{n,m}\)存图,某一位为\(1\)表示目标矩阵上该位为B,\(0\)表示为W.特别地,边界上为\(0\).
定义数组\(sum_{n,m}\),\(sum_{i,j}=map_{i,j}\oplus map_{i+1,j}\oplus map_{i,j+1}\oplus map_{i+1,j+1}\).
将\(map\)所有元素变为\(0\)等价于\(sum_{n,m}\)所有元素变为\(0\).
考虑四种操作对\(sum\)的影响.
首先,操作2,3是没有用的,可以被两次操作1代替.
为了方便,定义四元组\((x_1,y_1,x_2,y_2)\)表示左上角,右下角分别为\((x_1,y_1)\),\((x_2,y_2)\)的子矩阵.
若我们选择\((1,1,x,y)\)的矩阵翻转,仅有\(sum_{x,y}\)取反,花费一元.
若我们选择\((x,y,n,m)\)的矩阵反转,则\(sum_{x-1,y-1}\),\(sum_{x-1,m}\),\(sum_{n,y-1}\),\(sum_{n,m}\)取反,花费三元,改变四个格子.但是若进行两次操作4,\(sum_{n,m}\)取反两次,即不变,花费了6元改变了6个格子,这样我们不如用操作1.
统计下\(sum\)数组中\(1\)的数量,判断能否使用操作4即可.
代码
#include <iostream>
#include <cstdio>
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
int readc() {
char c = getchar();
while(c != 'W' && c != 'B')c = getchar();
return c;
}
const int N = 510;
int n , m;
bool map[N][N];
bool sum[N][N];
int main() {
n = read() , m = read();
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
map[i][j] = (readc() == 'B');
int ans = 0;
for(int i = n ; i > 0 ; i--)
for(int j = m ; j > 0 ; j--)
ans += (sum[i][j] = map[i + 1][j] ^ map[i][j + 1] ^ map[i + 1][j + 1] ^ map[i][j]);
if(sum[n][m])
for(int i = 1 ; i < n ; i++)
for(int j = 1 ; j < m ; j++)
if(sum[i][j] && sum[i][m] && sum[n][j]) {
cout << --ans;
return 0;
}
cout << ans;
return 0;
}