洛谷[P3392 涂国旗] {暴力枚举}

题目描述

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

从最上方若干行（至少一行）的格子全部是白色的； 接下来若干行（至少一行）的格子全部是蓝色的； 剩下的行（至少一行）全部是红色的； 现有一个棋盘状的布，分成了 N 行 M 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。

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

输入格式

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

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

输出格式

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

输入输出样例

输入 4 5 WRWRW BWRWB WRWRW RWBWR 输出 11

说明/提示

样例解释 目标状态是：

WWWWW B B B B B R R R R R R R R R R 一共需要改 11 个格子。

数据范围 对于 100% 的数据，N,M≤50。

解题思路

       首先根据ASCII码的数值，进行映射，获取每一行中原来涂白色、蓝色、红色的个数。注：ASCII（B:66,R:82,W:87)        将旗帜分为三段：1-i , i+1-j, j-N。因为每种颜色最少一行，所以白色最多只能到倒数第三行（N-2），蓝色最多只能到倒数第二行(N-1)。

完整代码

#include<bits/stdc++.h> using namespace std; int a[51][30]; char b[51][51]; int main() { int N,M; scanf("%d %d",&N,&M); for(int i=1;i<=N;i++)//输入卡掉了 { scanf("%s",b[i]); for(int j=0;j<=M-1;j++) a[i][b[i][j]-65]++;//映射 } int sum=1e9; for(int i=1;i<=N-2;i++)//行小于等于i时是白色，大于i小于等于j是蓝色，大于j小于等于N是红色 { for(int j=i+1;j<=N-1;j++) { int ans=0; for(int p=1;p<=i;p++) { ans+=M-a[p][22];//涂白色 } for(int p=i+1;p<=j;p++) { ans+=M-a[p][1];//涂蓝色 } for(int p=j+1;p<=N;p++) { ans+=M-a[p][17];//涂红色 } sum=min(ans,sum); } } printf("%d",sum); return 0; }