涂国旗

题目描述

某国法律规定，只要一个由 $N\times M$ 个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）

• 从最上方若干行（至少一行）的格子全部是白色的；
• 接下来若干行（至少一行）的格子全部是蓝色的；
• 剩下的行（至少一行）全部是红色的；

现有一个棋盘状的布，分成了 $N$ 行 $M$ 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。

小a很懒，希望涂最少的格子，使这块布成为一个合法的国旗。

输入格式

第一行是两个整数 $N,M$。

接下来 $N$ 行是一个矩阵，矩阵的每一个小方块是W（白），B（蓝），R（红）中的一个。

输出格式

一个整数，表示至少需要涂多少块。

样例 #1

样例输入 #1

4 5
WRWRW
BWRWB
WRWRW
RWBWR

样例输出 #1

11

提示

样例解释

目标状态是：

WWWWW
BBBBB
RRRRR
RRRRR

一共需要改 $11$ 个格子。

数据范围

对于 $100\%$ 的数据，$N,M\le 50$。

思路

红蓝白条都要有，以1条红条1条白条为起点开始搜索。
将某行补成红条需要涂的格数即该行蓝格和白格的格数之和，补成蓝条或白条同理。

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 55;int n, m;
int wr[maxn][maxn];
int b[maxn][maxn];
char a[maxn][maxn];
int vis[maxn][maxn];
int ans;
queue<pair<int, int>> q;struct S
{int w = 0;int b = 0;int r = 0;
} c[maxn];void bfs()
{memset(vis, 0, sizeof(vis));q.push(mp(0, 0));while (!q.empty()){pair<int, int> f = q.front();q.pop();int w = f.first;int r = f.second;if (!vis[w][r]){vis[w][r] = 1;for (int i = w + 1; i <= n - r; i++){b[w][r] += c[i].w + c[i].r;}if (n - w - r - 1 > 0){q.push(mp(w + 1, r));q.push(mp(w, r + 1));wr[w + 1][r] = wr[w][r] + c[w + 1].b + c[w + 1].r;wr[w][r + 1] = wr[w][r] + c[n - r].b + c[n - r].w;}}}
}int main()
{memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));memset(wr, 0, sizeof(wr));cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];switch (a[i][j]){case 'W':c[i].w++;break;case 'B':c[i].b++;break;case 'R':c[i].r++;break;}}}bfs();ans = wr[1][1] + b[1][1];for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (n - i - j > 0){ans = min(ans, wr[i][j] + b[i][j]);}}}cout << ans << endl;return 0;
}