2432: 【普及-】【P3392】涂国旗

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：5 解决：2

题目描述

某国法律规定，只要一个由 lns="http://www.w3.org/1998/Math/MathML">�×� 个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）

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

现有一个棋盘状的布，分成了 lns="http://www.w3.org/1998/Math/MathML">� 行 lns="http://www.w3.org/1998/Math/MathML">� 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。

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

输入

第一行是两个整数 lns="http://www.w3.org/1998/Math/MathML">�,�。

接下来 lns="http://www.w3.org/1998/Math/MathML">� 行是一个矩阵，矩阵的每一个小方块是W（白），B（蓝），R（红）中的一个。

输出

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

样例输入 复制 

4 5
WRWRW
BWRWB
WRWRW
RWBWR

样例输出 复制 

11

提示

样例解释

目标状态是： 

WWWWW
BBBBB
RRRRR
RRRRR

一共需要改 lns="http://www.w3.org/1998/Math/MathML">11 个格子。

数据范围

对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，lns="http://www.w3.org/1998/Math/MathML">�,�≤50。 

#include<bits/stdc++.h>
using namespace std;
char a[60][60];
int n,m,ans=2500;
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++){
        	cin>>a[i][j];
		}
		getchar();    	
	}
    for (int i=1;i<=n-2;i++) {
    	for (int j=i+1;j<=n-1;j++) {
    		int cnt=0;
    		for (int x=1;x<=i;x++)
    			for (int y=1;y<=m;y++)
    			    if (a[x][y]!='W') cnt++;
    		for (int x=i+1;x<=j;x++)
    			for (int y=1;y<=m;y++)
    			    if (a[x][y]!='B') cnt++;
    		for (int x=j+1;x<=n;x++)
    			for (int y=1;y<=m;y++)
    			    if (a[x][y]!='R') cnt++;
			ans=min(ans,cnt);    			    
		}
	}
	cout<<ans;
	return 0;
}

来源/分类

提交提交记录统计露一手!