2091. Mini Paint

单点时限: 2.0 sec

内存限制: 256 MB

You have been given a String of picture. Each character in picture represents a space in the picture. A ‘B’ designates a space that needs to be painted black, and a ‘W’ denotes a space that must be painted white. The painting device you have been given only makes horizontal strokes, of any length, exactly one space high. In addition, it can only use 1 color at a time. Due to the nature of the paint, a space cannot be painted twice. For example, the following picture could be colored in 6 distinct strokes:

picture = {“BBBBBBBBBBBBBBB”,

“WWWWWWWWWWWWWWW”,

“WWWWWWWWWWWWWWW”,

“WWWWWBBBBBWWWWW”}

You would use 1 stroke for each of the first 3 lines, and then 3 strokes on the last line.

This wouldn’t be an issue if we had forever to paint the picture. Unfortunately, you only have enough time to make at most maxStrokes distinct strokes. Any more strokes would put you past your deadline. Since finishing on time is more important than getting it perfect, you are willing to mispaint some of the spaces. Return the fewest number of spaces that can be mispainted while still using no more than maxStrokes strokes. An unpainted space is considered mispainted.

输入格式

There are many tests.Each test case first line two integer m,n describle the picture,then the next m*n characters,at last line a interger t is maxStrokes.

-picture will contain between 1 and 50 elements inclusive.

-Each element of picture will contain between 1 and 50 characters inclusive.

-Each element of picture will contain the same number of characters.

-Each character in each element of picture will be (quotes for clarity) ‘B’ or ‘W’.

-maxStrokes will be between 0 and 3000 inclusive.

输出格式

output the fewest number of spaces that can be mispainted while still using no more than maxStrokes strokes.

样例

Input
4 15
BBBBBBBBBBBBBBB
WWWWWWWWWWWWWWW
WWWWWWWWWWWWWWW
WWWWWBBBBBWWWWW
6 30
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
100
Output
0
40
Exactly enough strokes to finish the job.

2 人解决,4 人已尝试。

4 份提交通过,共有 7 份提交。

8.8 EMB 奖励。

创建: 11 年,10 月前.

修改: 2 年,5 月前.

最后提交: 7 年,8 月前.

来源: TC

题目标签