洛谷题单指南-暴力枚举-P3392 涂国旗

原题链接：https://www.luogu.com.cn/problem/P3392

题意解读：此题枚举白、蓝、红所有可能的行数组合，依次逐行判断每个方格，是否需要染色，计算最少的染色次数即可。

解题思路：

总行数是n，

先考虑白色，第一行必是白色，最后一行必是红色，至少有一行蓝色，因此白色行数的范围是1 ~ n - 2

再考虑蓝色，前面白色行数为i，至少有一行红色，因此蓝色行数的范围是n - i - 1

最后考虑红色，白色行数为i，蓝色行数为j，那么红色行数可以直接计算n - i - j

枚举每种白、蓝、红的组合即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 55;

char a[N][N];
int n, m;
int ans = 2e9;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    //白：1~n-2，蓝：1~n-白-1，红：n-白-蓝
    for(int i = 1; i <= n - 2; i++)
    {
        for(int j = 1; j <= n - i - 1; j++)
        {
            int k = n - i - j; //红色行数
            int cnt = 0;
            
            int x = 1;
            for(; x <= i; x++)
                for(int y = 1; y <= m; y++)
                    if(a[x][y] != 'W') cnt++; //涂为白色

            for(; x <= i + j; x++)
                for(int y = 1; y <= m; y++)
                    if(a[x][y] != 'B') cnt++; //涂为蓝色

            for(; x <= n; x++)
                for(int y = 1; y <= m; y++)
                    if(a[x][y] != 'R') cnt++; //涂为红色

            ans = min(ans, cnt);
        }
    }

    cout << ans;

    return 0;
}