题目描述

难度分:$2600$

输入$n$、$m(1 \leq n,m \leq 500)$和$n$行$m$列的矩阵，只包含字符B和W。

你需要把所有B都变成W。
有如下四种操作：

• 操作$1$：支付$1$元，选择一个包含矩阵左上角$(1,1)$的子矩阵，将其翻转，即W变成B，B变成W。
• 操作$2$：支付$2$元，选择一个包含矩阵左下角$(n,1)$的子矩阵，将其翻转。
• 操作$3$：支付$4$元，选择一个包含矩阵右上角$(1,m)$的子矩阵，将其翻转。
• 操作$4$：支付$3$元，选择一个包含矩阵右下角$(n,m)$的子矩阵，将其翻转。

把所有B都变成W，最小总花费是多少？

输入样例$1$

3 3
WWW
WBB
WBB

输出样例$1$

3

输入样例$2$

10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW

输出样例$2$

74

算法

位运算+二维差分

神仙题，根本没思路，只能学习题解。首先把白色作为$0$，黑色作为$1$，将字符矩阵转化为整数矩阵$a$。

接着发现操作$2$和$3$没什么用，假设操作$2$要翻转一个以$(n,1)$为左下角、$(x,y)$为右上角的子矩阵，可以发现利用$2$次操作$1$也可以达到相同的效果，先翻转以$(1,1)$为左上角、$(n,y)$为右下角的子矩阵，再翻转以$(1,1)$为左上角、$(x-1,y)$为右下角的子矩阵。用$1$次操作$2$和用$2$次操作$1$代价是相同的，为了让策略更少使得问题简化，不使用操作$2$。

假设操作$3$要翻转一个以$(1,m)$为右上角、$(x,y)$为左下角的子矩阵，那么又可以用$2$次操作$1$来达成这个效果，先翻转左上角为$(1,1)$、右下角为$(x,m)$的子矩阵，再翻转左上角为$(1,1)$、右下角为$(x,y-1)$的子矩阵即可。而$2$次操作$1$的代价小于$1$次操作$3$的代价，所以操作$3$也不使用。

以上操作看着颇有二维差分的影子，所以令$p[i][j]=a[i][j+1] \oplus a[i+1][j] \oplus a[i][j] \oplus a[i+1][j+1]$，这样操作$1$就被转化为翻转$p[x][y]$（翻转以$(1,1)$为左上角、$(x,y)$为右下角的子矩阵）。而操作$4$就相当于翻转了$4$个数：$p[x-1][y-1]$、$p[x-1][m]$、$p[n][y-1]$、$p[n][m]$（满足$x \gt 1$或$y \gt 1$，否则可以用$1$次操作$1$来代替，作用的子矩阵左上角为$(x,y)$、右下角为$(n,m)$）。此时，任务就变成了要让$p$矩阵为全零矩阵。

这时候又发现使用超过一次操作$4$是不优的，因为$p[n][m]$被重复改变，那么使用两次操作$4$就只改变了$6$个格子的状态，并没有比使用$6$次操作$1$更好。这样就可以对$p$矩阵求和，初始化答案为只使用操作$1$的总开销。然后再遍历一遍$p$矩阵，如果发现存在$x \lt n$且$y \lt m$满足$p[x][y]=p[x][n]=p[n][y]=p[n][m]=1$，那么这$4$个格子的状态就可以通过$1$次操作$2$改变（代价$3$元），没必要用$4$次操作$1$（代价$4$元），可以少用$1$元钱。

复杂度分析

时间复杂度

处理出$a$矩阵和$p$矩阵的时间复杂度都是$O(nm)$，判断答案要不要减$1$也遍历了一次矩阵。因此，整个算法的时间复杂度就是$O(nm)$。

空间复杂度

除了输入的字符矩阵$s$，开辟了两个$O(nm)$空间的数组$a$和$p$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
int n, m, a[N][N], p[N][N];
char s[N][N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= m; j++) {
            a[i][j] = s[i][j] == 'B';
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ans += p[i][j] = (a[i][j] ^ a[i][j + 1] ^ a[i + 1][j] ^ a[i + 1][j + 1]);
        }
    }
    for(int i = 1, ok = 0; i < n && !ok; i++) {
        for(int j = 1; j < m && !ok; j++) {
            if(p[i][j] && p[i][m] && p[n][j] && p[n][m]) {
                ok = 1, ans--;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}