CF225C.Barcode

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You've got an $n×m$ pixel picture. Each pixel can be white or black. Your task is to change the colors of as few pixels as possible to obtain a barcode picture.

A picture is a barcode if the following conditions are fulfilled:

All pixels in each column are of the same color.
The width of each monochrome vertical line is at least $x$ and at most $y$ pixels. In other words, if we group all neighbouring columns of the pixels with equal color, the size of each group can not be less than $x$ or greater than $y$ .

输入格式

The first line contains four space-separated integers $n$ , $m$ , $x$ and $y$ ( $1<=n,m,x,y<=1000; x<=y$ ).

Then follow $n$ lines, describing the original image. Each of these lines contains exactly $m$ characters. Character "." represents a white pixel and "#" represents a black pixel. The picture description doesn't have any other characters besides "." and "#".

输出格式

In the first line print the minimum number of pixels to repaint. It is guaranteed that the answer exists.

输入输出样例

输入#1

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

输出#1

输入#2
```
2 5 1 1
#####
.....
```
输出#2
```
5
```

说明/提示

In the first test sample the picture after changing some colors can looks as follows:

 .##.. .##.. .##.. .##.. .##.. .##.. In the second test sample the picture after changing some colors can looks as follows:

 .#.#. .#.#. 

首页